/* solver.c */
/* Last Change: 2019/05/21 (Tue) 18:09:17. */

#include<limits.h>
#include"solver.h"
#include"io.h"
#include<stdio.h>
//#include <list>
#include <vector>
#include <algorithm>
//#include <bits/stdc++.h>
#include "router/router.hpp"
/* #include<stdlib.h> */
/* #include<string.h> */
/* #include<math.h> */
/* #include<time.h> */

#define SPACE 1

short int connected[MAXLINE]={0}; //if line connected:2, if one end:1, otherwize:0
short int board_beta[MAXSIZE][MAXSIZE]; //big board data
//edge:1~MAXLINE, line:-1~-MAXLINE, none:0, wall:SHRT_MIN
short int rank[MAXBLOCK+1];
short int done_block[MAXBLOCK+1];
short int board_str[900];
short int line_board[72][72];
short int mino_board[72][72];
short int put_data[72][72];
short int success=0;
short int answerw=0,answerh=0;
vector <int> mino_order;

void reset_board(void){
	int i,j;
	for(i=0;i<MAXSIZE;i++)
		for(j=0;j<MAXSIZE;j++)
			board_beta[i][j]=0;
	return;
}

void show_blocks(){
	int data[4][4];
	int i,j,k;
	for(i=1;i<blocks;i++){
		//printf("block #%d\n",i);
		for(j=1;j<=4;j++){
			//printf("x:%d y:%d edge:%d\n",block_data[i][j][0],block_data[i][j][1],block_data[i][j][2]);
		}
	}
	return;
}

void read_data(void){
	answerw=W;
	answerh=H;
	//show_blocks();
	return;
}


void translate(void){
	int i,j;
	int minw=MAXSIZE-1,maxw=0,minh=MAXSIZE-1,maxh=0;
	for(i=0;i<MAXSIZE;i++){
		for(j=0;j<MAXSIZE;j++){
			if(board_beta[i][j]){
				if(i>maxw)
					maxw=i;
				if(i<minw)
					minw=i;
				if(j>maxh)
					maxh=j;
				if(j<minh)
					minh=j;
				if(board_beta[i][j]==SHRT_MIN)
					board_beta[i][j]=0;
				else if(board_beta[i][j]<0)
					board_beta[i][j]=-board_beta[i][j];
			}
		}
	}
	for(i=1;i<=blocks;i++){
		/* block_data[i][0]-=minw; */
		/* block_data[i][1]-=minh; */
	}
	for(i=0;i<maxw-minw;i++){
		for(j=0;j<maxh-minh;j++){
			put_data[i][j]=board_beta[i+minw][j+minh];
		}
	}
	return;
}

void init_mino(void){
	int i;
	for(i=1;i<MAXBLOCK+2;i++){
		done_block[i]=0;
	}
}

int check_around(int x,int y){
	if(put_data[x+1][y] || put_data[x][y+1] || put_data[x-1][y] || put_data[x][y-1]||
	put_data[x+1][y+1]||put_data[x+1][y-1]||put_data[x-1][y-1]||put_data[x-1][y+1]) return 1;
	else{
		return 0;
	}
}
void del_mino(int mino){
	int x,y;
	x=block_data[mino][0][0];
	y=block_data[mino][0][1];
	for(int i=1;i<5;i++){
		put_data[x+block_data[mino][i][0]][y+block_data[mino][i][1]]=0;
	}
	block_data[mino][0][0]=-1;
	block_data[mino][0][1]=-1;
}

int check_put_mino(int i,int x, int y,int flag){// check block#i can put on x,y
	for(int j=1;j<5;j++){
		if(x+block_data[i][j][0]>W-1){
			return 0;
		}
		if(y+block_data[i][j][1]>H-1){
			return 0;
		}
		if(put_data[x+block_data[i][j][0]][y+block_data[i][j][1]]!=0){
			return 0;
		}
		if(flag==0){
			if(check_around(x+block_data[i][j][0],y+block_data[i][j][1])){
				return 0;
			}
		}
	}
	return 1;
}


int data_mino(int i, int x,int y,int flag){
	//std::cout << "put mino "<< i << " on " << x <<" " << y << std::endl;
	for(int j=0;j<100;j++){
		if(check_put_mino(i,x,y,flag)){
			for(int l=1;l<5;l++){
				mino_board[x+block_data[i][l][0]][y+block_data[i][l][1]]=i;
				if(l==2 && block_data[i][l][2]==-1){
					block_data[i][0][0]=x;
					block_data[i][0][1]=y;
					return 1;
				}
				if(block_data[i][l][2]!=0){
					put_data[x+block_data[i][l][0]][y+block_data[i][l][1]]=block_data[i][l][2];
				}else{
					put_data[x+block_data[i][l][0]][y+block_data[i][l][1]]=-1;
				}
			}
			block_data[i][0][0]=x;
			block_data[i][0][1]=y;
			 return 1;
		}
		x+=(j%2)*SPACE;
		y+=((j+1)%2)*SPACE;
		if(x>W || y>H) return 0;
	}
}

void put_mino(){
	int i,j,k,now;
	std::vector<int> order_w;
	std::vector<int> order_h;
	int map_w[4]={0,0,0,0};
	int map_h[4]={0,0,0,0};
	int len[MAXBLOCK+1];
	int check_block[100];//block in the order_w
	int done_block[100];//fixed block in the order_w
	int end;
	int flag=0;
	order_w.push_back(1); // start from block#1
	int index=0;
	int next=0;
	int x=0;
	int another=0;
	auto itr=order_w.begin();
	for(int i=0;i<=blocks;i++){
		done_block[i]=0;
	}
	while(true){
		another=0;
		for(index=order_w.size()-1;index>=0;index--){ // find next block
			if(done_block[order_w[index]]==0){
				next=order_w[index];
				another=1;
				//done_block[next]=1;
				//check_block[next]=1;
				break;
			}
		}
		if(index==-1){
			for(index=blocks;index>0;index--){
				//std::cout << done_block[index];
				if(done_block[index]==0){
					next=index;
					break;
				}
			}
			//std::cout << endl;
			if(index==0) break; // if all blocks are searched
		}
		if(index==-1) break; // if all blocks are searched
		if(another){
			itr=order_w.begin();
			for(int i=0;i<index;i++){//remove index itretor
				itr++;
			}
			order_w.erase(itr);
		}else{
			itr=order_w.end();
		}
		//std::cout << "block#"<<next << std::endl;
		//make block order
		if(block_data[next][1][0]==block_data[next][2][0]){
			//std::cout << "patern 1"<< std::endl;
			if(block_data[next][2][0]==block_data[next][3][0] || block_data[next][2][1]==block_data[next][4][1]){//for I-mino1,L-mino1,T-mino1,S-mino1,Lf-mino4
				map_w[0]=block_data[next][1][2];
				map_w[1]=block_data[next][2][2];
				map_w[2]=block_data[next][3][2];
				map_w[3]=block_data[next][4][2];
			}else{
				map_w[0]=block_data[next][1][2];
				map_w[1]=block_data[next][2][2];
				map_w[2]=block_data[next][4][2];
				map_w[3]=block_data[next][3][2];
			}
		}else if(block_data[next][1][1]==block_data[next][4][1]){//I-mino2
			//std::cout << "patern 2"<< std::endl;			
				map_w[0]=block_data[next][1][2];
				map_w[1]=block_data[next][2][2];
				map_w[2]=block_data[next][3][2];
				map_w[3]=block_data[next][4][2];
		}else if(block_data[next][1][1]==block_data[next][2][1]){
			//std::cout << "patern 3"<< std::endl;
			if(block_data[next][1][0]==block_data[next][4][0]){//L-mino4
				map_w[0]=block_data[next][1][2];
				map_w[1]=block_data[next][4][2];
				map_w[2]=block_data[next][2][2];
				map_w[3]=block_data[next][3][2];
			}else{//S-mino2,Sf,mino2,O-mino,L-mino3,Lf-mino1,Lf-mino3,T-mino4
				map_w[0]=block_data[next][1][2];
				map_w[1]=block_data[next][3][2];
				map_w[2]=block_data[next][4][2];
				map_w[3]=block_data[next][2][2];
			}
		}else if(block_data[next][2][1]==block_data[next][3][1]&&block_data[next][3][0]==block_data[next][4][0]){
			//std::cout << "patern 4"<< std::endl;
				map_w[0]=block_data[next][2][2];
				map_w[1]=block_data[next][4][2];
				map_w[2]=block_data[next][3][2];
				map_w[3]=block_data[next][1][2];
		}else{
			//std::cout << "patern 5"<< std::endl;
			map_w[0]=block_data[next][1][2];
			map_w[1]=block_data[next][2][2];
			map_w[2]=block_data[next][3][2];
			map_w[3]=block_data[next][4][2];
		}
		/*for(int k=0;k<4;k++){
			std::cout << map_w[k]<<" ";
		}*/
		//std::cout << std::endl;
		//done_block[next]=1;
		for(int k=0;k<4;k++){
			if(map_w[k]==0) continue;
			flag=0;
			for(int i=1;i<=blocks;i++){
				if(i==next) continue;
				for(int j=1;j<=4;j++){// find pair block
					if(block_data[i][j][2]==map_w[k]){
						//std::cout << k << " " << map_w[k]<< "found at " << i << std::endl;
						if(check_block[i]==1 || done_block[i]==1){
							map_w[k]=0;
						}else{
							check_block[i]=1;
							map_w[k]=i;
						}
						flag=1;
						break;
					}
					//if(j==4) std::cout << "not found " << map_w[k] <<std::endl;
				}
				if(flag==1) break;
			}
		}
		for(int i=0;i<4;i++){
			if(i==2){
				itr=order_w.insert(itr,next);
				itr++;
			}
			if(map_w[i]==0|| map_w[i]==-1) continue;
			itr=order_w.insert(itr,map_w[i]);
			itr++;
		}
		done_block[next]=1;
		/*for(int i=0;i<order_w.size();i++){
			printf("%d ",order_w[i]);
		}
		printf("\n");*/
		x++;
		//if(x==10)break;
	}//end of while ture for width
	/*printf("answer is \n");
	for(int i=0;i<order_w.size();i++){
		printf("%d ",order_w[i]);
	}
	printf("\n");*/




	//printf("\n\nstart making order of height\n");
	for(int i=1;i<=blocks;i++){//init status
		check_block[i]=0;
		done_block[i]=0;
	}
	next=0;
	itr=order_h.begin();
	order_h.push_back(1);
	another=0;
	while(true){//start of while true for height
		another=0;
		for(index=order_h.size()-1;index>=0;index--){ // find next block
			if(done_block[order_h[index]]==0){
				next=order_h[index];
				another=1;
				break;
			}
		}
		if(index==-1){
			//std::cout << "left block search" << std::endl;
			for(index=blocks;index>0;index--){
				if(done_block[index]==0){
					next=index;
					break;
				}
			}
			if(index==0) break; // if all blocks are searched
		}
		//std::cout << "now" << std::endl;
		if(another==1){
			itr=order_h.begin();
			for(int i=0;i<index;i++){//remove index itretor
				itr++;
			}
			order_h.erase(itr);
		}else{
			itr=order_h.end();
		}
		/*std::cout << "block#"<<next << std::endl;
		for(int k=1;k<=4;k++){
			std::cout << block_data[next][k][0];
		}
		std::cout << std::endl;*/
		//make block order
		if(block_data[next][1][1]==block_data[next][2][1]){
			//std::cout << "patern 1"<< std::endl;
			if(block_data[next][3][1]==block_data[next][4][1]){//for I-mino2,S-mino2,Sf-mino2,O-mino
				map_h[0]=block_data[next][1][2];
				map_h[1]=block_data[next][2][2];
				map_h[2]=block_data[next][4][2];
				map_h[3]=block_data[next][3][2];
			}else{//for L-mino3,L-mino4,Lf-mino2,Lf-mino3,T-mino4
				map_h[0]=block_data[next][1][2];
				map_h[1]=block_data[next][2][2];
				map_h[2]=block_data[next][3][2];
				map_h[3]=block_data[next][4][2];
			}
		}else if(block_data[next][1][0]==block_data[next][4][0]){//I-mino1
			//std::cout << "patern 2"<< std::endl;			
				map_h[0]=block_data[next][1][2];
				map_h[1]=block_data[next][2][2];
				map_h[2]=block_data[next][3][2];
				map_h[3]=block_data[next][4][2];
		}else if(block_data[next][1][0]==block_data[next][2][0]){
			//std::cout << "patern 3"<< std::endl;
			if(block_data[next][3][1]==block_data[next][4][1]){//L-mino1,Lf-mino1
				map_h[0]=block_data[next][1][2];
				map_h[1]=block_data[next][2][2];
				map_h[2]=block_data[next][4][2];
				map_h[3]=block_data[next][3][2];
			}else{//T-mino1,Lf-mino4,S-mino1
				map_h[0]=block_data[next][1][2];
				map_h[1]=block_data[next][3][2];
				map_h[2]=block_data[next][4][2];
				map_h[3]=block_data[next][2][2];
			}
		}else if(block_data[next][1][0]==block_data[next][3][0]&&block_data[next][4][1]!=1){//T-mino3,Sf-mino1
			//std::cout << "patern 4"<< std::endl;
				map_h[0]=block_data[next][2][2];
				map_h[1]=block_data[next][1][2];
				map_h[2]=block_data[next][3][2];
				map_h[3]=block_data[next][4][2];
		}else{//L-mino2,T-mino2
			//std::cout << "patern 5"<< std::endl;
			map_h[0]=block_data[next][2][2];
			map_h[1]=block_data[next][1][2];
			map_h[2]=block_data[next][4][2];
			map_h[3]=block_data[next][3][2];
		}
		/*for(int k=0;k<4;k++){
			std::cout << map_h[k]<<" ";
		}
		std::cout << std::endl;*/
		//done_block[next]=1;
		for(int k=0;k<4;k++){
			if(map_h[k]==0) continue;
			flag=0;
			for(int i=1;i<=blocks;i++){
				if(i==next) continue;
				for(int j=1;j<=4;j++){// find pair block
					if(block_data[i][j][2]==map_h[k]){
						//std::cout << k << " " << map_h[k]<< "found at " << i << std::endl;
						if(check_block[i]==1 || done_block[i]==1){
							map_h[k]=0;
						}else{
							check_block[i]=1;
							map_h[k]=i;
						}
						flag=1;
						break;
					}
					//if(j==4) std::cout << "not found " << map_w[k] <<std::endl;
				}
				if(flag==1) break;
			}
		}
		for(int i=0;i<4;i++){
			if(i==2){
				itr=order_h.insert(itr,next);
				itr++;
			}
			if(map_h[i]==0|| map_h[i]==-1) continue;
			itr=order_h.insert(itr,map_h[i]);
			itr++;
		}
		/*
		for(int i=0;i<order_h.size();i++){
			printf("%d ",order_h[i]);
		}
		printf("\n");*/
		done_block[next]=1;
		//x++;
		//if(x==1)break;
	}//end of while ture for height

	/*printf("width is \n");
	for(int i=0;i<order_w.size();i++){
		printf("%d ",order_w[i]);
	}
	printf("\n");

	printf("height is \n");
	for(int i=0;i<order_h.size();i++){
		printf("%d ",order_h[i]);
	}
	printf("\n");
*/
	int put_block[100];
	int height_c=0,width_c=1;
	int next_put=1;
	int max_w=0;
	int max_h=0;
	for(int i=0;i<blocks;i++){
		height_c=height_c+SPACE;
		width_c=0;
		max_w=0;
		max_h=0;
		next_put = order_h[i];
		for(int j=0;j<blocks;j++){
			if(order_w[j]==next_put) break;
			max_w=0;
			for(k=1;k<5;k++){
				if(block_data[order_w[j]][k][0]>max_w){
					 max_w = block_data[order_w[j]][k][0];
				}	
			}
			//std::cout<< "add " << order_w[j] << " mino " << max_w+1 << std::endl;
			width_c+=max_w+1;
			width_c+=SPACE;
		}
		//std::cout << width_c << std::endl;
		//std::cout << height_c << std::endl;
		//if(max_w==0) data_mino(next_put,width_c,height_c,0);
		//else data_mino(next_put,width_c+SPACE,height_c,0);
		data_mino(next_put,width_c+SPACE,height_c,0);
		for(int k=1;k<5;k++){
			if(block_data[next_put][k][1]>max_h) max_h = block_data[next_put][k][1];
		}
		height_c+=max_h+1;
	}
	//print_answer();
	//int next;
	int mino_x,mino_y;
}
void make_board_str(int size_x,int size_y){
	for(int y = 0; y < size_y; y++) {
		for(int x = 0; x < size_x; x++) {
			int idx = y * size_x + x;
			board_str[idx] = put_data[x][y];
		}
	}
}
void fix_to_board(int size_x, int size_y){
	for(int y = 0; y < size_y; y++) {
		for(int x = 0; x < size_x; x++) {
			int idx = y * size_x + x;
			line_board[x][y] = board_str[idx];
			//put_data[x][y] = board_str[idx];
		}

	}
}
void make_small(){
	int i,j;
	int maxw=0,maxh=0;
	for(i=0;i<W;i++){
		for(j=0;j<H;j++){
			if(line_board[i][j]){
				if(i>maxw)
					maxw=i;
				if(j>maxh)
					maxh=j;
			}
		}
	}
	W=maxw+2;
	H=maxh+2;
	//cout << "W is " << W << " H is " << H << endl;
	return;
}


void make_answer(){
	make_small();
	for(int i=0;i<H;i++){
		for(int j=0;j<W;j++){
			board_data[i][j]=line_board[i][j];
		}
	}

}

int line(){
	make_board_str(W,H);
	//std::cout <<  lfsr <<std::endl;
	int status = router(W, H, line_num, board_str);
	fix_to_board(W,H);
		if(status){
		//std::cout << "success to line" << std::endl;
		make_answer();
		success=1;
	}else{
		//std::cout << "failed to line" << std::endl;
	}
	return status;
}

void del_mino_line(int mino){
	int x,y;
	x=block_data[mino][0][0];
	y=block_data[mino][0][1];
	for(int i=1;i<5;i++){
		line_board[x+block_data[mino][i][0]][y+block_data[mino][i][1]]=0;
	}
}

int check_move_mino(int i,int x, int y){// check block#i can put on x,y
	for(int j=1;j<5;j++){
		if(block_data[i][j][2]==-1) return 1;
		if(x+block_data[i][j][0]<0){
			return 0;
		}
		if(y+block_data[i][j][1]<0){
			return 0;
		}
		//cout << "check to " << x+block_data[i][j][0]+block_data[i][0][0] << " " << y+block_data[i][j][1]+block_data[i][0][1] << endl;
		//if(line_board[x+block_data[i][j][0]+block_data[i][0][0]][y+block_data[i][j][1]+block_data[i][0][1]]!=0 && line_board[x+block_data[i][j][0]+block_data[i][0][0]][y+block_data[i][j][1]+block_data[i][0][1]]!=put_data[block_data[i][j][0]+block_data[i][0][0]][block_data[i][j][1]+block_data[i][0][1]]){
		//	return 0;
		//}
		if(line_board[x+block_data[i][j][0]][y+block_data[i][j][1]]!=0){
			return 0;
		}
//		line_board[x+block_data[i][j][0]+block_data[i][0][0]][y+block_data[i][j][1]+block_data[i][0][1]]=0;
	}
	return 1;
}


int move_mino(int mino,int x, int y){ //1:success 2:failed
	int move_x=0,move_y=0;
	int mino_x,mino_y;
	//cout << "move from" << block_data[mino][0][0]<<" "<<block_data[mino][0][1]<< endl;
	for(int i=1;i<=y;i++){
		if(block_data[mino][0][1]-i<0) break;
		if(check_move_mino(mino,-move_x,-i)){
			move_y=i;
		}else{
			break;
		}
	}
	for(int i=1;i<=x;i++){
		if(block_data[mino][0][0]-i<0) break;
		if(check_move_mino(mino,-i,-move_y)){
			move_x=i;
		}else{
			break;
		}
	}
	//std::cout << "mino " << mino << " can move " << move_x << " " << move_y << std::endl;
	if(move_x!=0 || move_y!=0){
		mino_x=block_data[mino][0][0];
		mino_y=block_data[mino][0][1];
		del_mino(mino);
		data_mino(mino,mino_x-move_x,mino_y-move_y,1);
		return 1;
	}else{
		return 0;
	}
}

int set_line(int mino){// 
	for(int i=1;i<=4;i++){
		if(block_data[mino][i][2]==0) continue;
		if(line_board[block_data[mino][0][0]+block_data[mino][i][0]][block_data[mino][0][1]+block_data[mino][i][1]-1]==block_data[mino][i][2]) return block_data[mino][i][2]; 
	}
	for(int i=1;i<=4;i++){
		if(block_data[mino][i][2]==0) continue;
		if(line_board[block_data[mino][0][0]+block_data[mino][i][0]-1][block_data[mino][0][1]+block_data[mino][i][1]]==block_data[mino][i][2]) return block_data[mino][i][2];
	}
	return 0;
}

int move_dir(int mino, int l){// 1:left 0:up
	for(int i=1;i<=4;i++){
		if(block_data[mino][i][2]!=l) continue;
		if(line_board[block_data[mino][0][0]+block_data[mino][i][0]-1][block_data[mino][0][1]+block_data[mino][i][1]]==block_data[mino][i][2]) return 1; 
		if(line_board[block_data[mino][0][0]+block_data[mino][i][0]][block_data[mino][0][1]+block_data[mino][i][1]-1]==block_data[mino][i][2]) return 0;
	}
	return -1;
}

int move_along_line(int mino, int l,int dir,int check_num){
	int count=1,num=0;
	int new_x=block_data[mino][0][0],new_y=block_data[mino][0][1],flag=0;
	int mino_x=block_data[mino][0][0],mino_y=block_data[mino][0][1];
	for(int i=1;i<=4;i++){
		if(block_data[mino][i][2]==l){
			num=i;
			break;
		}
	}
	del_mino_line(mino);
	del_mino(mino);
	while(true){
		flag=0;
		if(dir==1){
			if(line_board[mino_x+block_data[mino][check_num][0]-count][mino_y+block_data[mino][check_num][1]]!=l) break;
			for(int i=1;i<=4;i++){
				//cout << i << endl;
				if(mino_x+block_data[mino][i][0]-count<1){
					//cout << "out of grid x " << endl;
					flag=1;
					break;
				}
				//if(i==check_num) continue;
				if(line_board[mino_x+block_data[mino][i][0]-count][mino_y+block_data[mino][i][1]]!=block_data[mino][i][2] && line_board[mino_x+block_data[mino][i][0]-count][mino_y+block_data[mino][i][1]]!=0){
			// if any block numbers in mino are not 0/same as the target cell 
					if(mino_x+block_data[mino][i][0]-count<2){ //see one more cell
						flag=1;
						break;
					}
					if(line_board[mino_x+block_data[mino][i][0]-count][mino_y+block_data[mino][i][1]]==l && (line_board[mino_x+block_data[mino][i][0]-count-1][mino_y+block_data[mino][i][1]]==0 || line_board[mino_x+block_data[mino][i][0]-count-1][mino_y+block_data[mino][i][1]]==l) &&put_data[mino_x+block_data[mino][i][0]-count-1][mino_y+block_data[mino][i][1]]==0){
						//cout <<"continue" << endl;
						//cout <<  mino_x+block_data[mino][i][0]-count << " " <<  mino_y+block_data[mino][i][1] << " " << line_board[mino_x+block_data[mino][i][0]-count][mino_y+block_data[mino][i][1]] <<endl;
						//cout <<  mino_x+block_data[mino][i][0]-count-1 << " " <<  mino_y+block_data[mino][i][1] << " " << line_board[mino_x+block_data[mino][i][0]-count-1][mino_y+block_data[mino][i][1]] <<endl;
						
						//line_board[mino_x+block_data[mino][i][0]-count-1][mino_y+block_data[mino][i][1]]=l;
						continue;
					}
					flag=1;
					//cout << "cannot move x" << endl;
					//cout << i << " " << check_num << endl;
					break;
				}else{
					//cout << "pass x" << endl;
				}
				if(line_board[mino_x+block_data[mino][i][0]-count][mino_y+block_data[mino][i][1]]==l && (line_board[mino_x+block_data[mino][i][0]-count-1][mino_y+block_data[mino][i][1]]!=0 && line_board[mino_x+block_data[mino][i][0]-count-1][mino_y+block_data[mino][i][1]]!=l)){
					flag=1;
					/*cout << "break" << endl;
					cout <<  mino_x+block_data[mino][i][0]-count << " " <<  mino_y+block_data[mino][i][1] << " " << line_board[mino_x+block_data[mino][i][0]-count][mino_y+block_data[mino][i][1]] <<endl;
					cout <<  mino_x+block_data[mino][i][0]-count-1 << " " <<  mino_y+block_data[mino][i][1] << " " << line_board[mino_x+block_data[mino][i][0]-count-1][mino_y+block_data[mino][i][1]] <<endl;
					*/break;
				}
				line_board[mino_x+block_data[mino][check_num][0]-count][mino_y+block_data[mino][check_num][1]]=0;
			}
			if(flag) break;
			new_x--;
			line_board[mino_x+block_data[mino][check_num][0]-count][mino_y+block_data[mino][check_num][1]]=0;
			//cout << "move left" << endl;		
		}else{
			if(line_board[mino_x+block_data[mino][check_num][0]][mino_y+block_data[mino][check_num][1]-count]!=l) break;
			for(int i=1;i<=4;i++){
				if(mino_y+block_data[mino][i][1]-count<1){
					flag=1;
					//cout << "out of grid y" << endl;
					 break;
				}
				//if(i==check_num) continue;
				if(line_board[mino_x+block_data[mino][i][0]][mino_y+block_data[mino][i][1]-count]!=block_data[mino][i][2] && line_board[mino_x+block_data[mino][i][0]][mino_y+block_data[mino][i][1]-count]!=0){
					if(mino_y+block_data[mino][i][1]-count<2){ //see one more cell
						flag=1;
						break;
					}
					if(line_board[mino_x+block_data[mino][i][0]][mino_y+block_data[mino][i][1]-count]==l && (line_board[mino_x+block_data[mino][i][0]][mino_y+block_data[mino][i][1]-count-1]==l || line_board[mino_x+block_data[mino][i][0]][mino_y+block_data[mino][i][1]-count-1]==0)){
						line_board[mino_x+block_data[mino][i][0]][mino_y+block_data[mino][i][1]-count-1]=l;
						continue;
					}
					flag=1;
					//cout << "can not move y" << endl;
					//cout << i << " " << check_num << endl;
					break;
				}else{
					//cout << "pass" << endl;
				}
				if(line_board[mino_x+block_data[mino][i][0]][mino_y+block_data[mino][i][1]-count]==l && (line_board[mino_x+block_data[mino][i][0]][mino_y+block_data[mino][i][1]-count-1]!=0 && line_board[mino_x+block_data[mino][i][0]][mino_y+block_data[mino][i][1]-count-1]!=l)){
					flag=1;
					//cout << "break" << endl;
					break;
				}	
			}
			if(flag) break;
			new_y--;
			line_board[mino_x+block_data[mino][check_num][0]][mino_y+block_data[mino][check_num][1]-count]=0;
		}
		count ++;
	}
	if(count!=1){
		data_mino(mino,new_x,new_y,1);
		return 1;
	}else{
		data_mino(mino,mino_x,mino_y,1);
		return 0;
	}

}

int set_num(int mino,int line){
	for(int i=1;i<=4;i++){
		if(block_data[mino][i][2]==line) return i;
	}
}

int move2line(){
	vector< pair<int,int>> move_order;
	int move=0,check_line=0,mino_dir,flag=0,check_num=0;
	//std::cout << "start move2line" << std::endl;
	for(int i=1;i<=blocks;i++){
		move_order.push_back(make_pair(block_data[i][0][0]+block_data[i][0][1],i));
	}
	sort(move_order.begin(),move_order.end());
	for(int i=0;i<blocks;i++){
		flag=0;
		check_line=set_line(move_order[i].second);
		check_num=set_num(move_order[i].second,check_line);
		if(check_line==0) continue; 
		//cout << "move " << move_order[i].second<< " line "  <<check_line << endl;
		mino_dir=move_dir(move_order[i].second,check_line);
		flag = move_along_line(move_order[i].second, check_line,mino_dir,check_num);
		if(flag){
			line();
			move=1;
		}
	}
	return move;
}

int move2space(){
	vector< pair<int,int>> move_order;
	int move=0,check_line=0,mino_dir,flag=0;
	int ch=0,cw=0,px,py;
	//std::cout << "start move2space" << std::endl;
	for(int i=1;i<=blocks;i++){
		move_order.push_back(make_pair(block_data[i][0][0]+block_data[i][0][1],i));
	}
	sort(move_order.begin(),move_order.end());
	for(int i=0;i<blocks;i++){
		ch=1;
		cw=1;
		px=block_data[move_order[i].second][0][0];
		py=block_data[move_order[i].second][0][1];
		del_mino_line(move_order[i].second);
		//cout << "move " << move_order[i].second << " at move2space" << endl;
		while(check_move_mino(move_order[i].second,px-ch,py)){
			ch++;
		}
		while(check_move_mino(move_order[i].second,px,py-cw)){
			cw++;
		}
		if(ch==1 && cw ==1){
			line();
			continue;
		}
		flag=1;
		if(ch>cw){
			del_mino(move_order[i].second);
			data_mino(move_order[i].second,px-ch+1,py,1);
		}else{
			del_mino(move_order[i].second);
			data_mino(move_order[i].second,px,py-cw+1,1);
		}
		//cout << "ch " << ch << " cw " << cw << endl;
		if(line()==0){
			while(line()==0){
				if(ch>cw){
					ch--;
					del_mino(move_order[i].second);
					data_mino(move_order[i].second,px-ch+1,py,1);
				}else{
					cw--;
					del_mino(move_order[i].second);
					data_mino(move_order[i].second,px,py-cw+1,1);
				}
			}
		}

	}
	//cout << "end move2space" << endl;
	return flag;
}


int reshape(){
	vector< pair<int,int>> move_order;
	int next,limit=0,end=5;
	int flag=0;
	//std::cout << "start reshape" << std::endl;
	for(int i=1;i<=blocks;i++){
		move_order.push_back(make_pair(block_data[i][0][0]+block_data[i][0][1],i));
	}
	sort(move_order.begin(),move_order.end());
	for(int i=1;i<=blocks;i++){
		next=move_order[i-1].second;
		del_mino_line(next);
		while(true){
			if(move_mino(next,1,1)){
				//cout << "moved" << endl;
				flag=1;
			}else{
				break;
			}
			limit++;
			//cout << limit << endl;
			if(limit>=end) break;
		}
		if(flag){
			 if(line()==0) return 0;
		}
	}
	return flag;
}
void resize(){
	int i,j;
	int minw=W,maxw=0,minh=H,maxh=0;
	for(int i=0;i<W;i++){
		for(int j=0;j<H;j++){
			put_data[i][j]=0;
		}
	}
	for(i=0;i<W;i++){
		for(j=0;j<H;j++){
			if(board_data[i][j]){
				if(i>maxw)
					maxw=i;
				if(i<minw)
					minw=i;
				if(j>maxh)
					maxh=j;
				if(j<minh)
					minh=j;
			}
		}
	}
	for(i=0;i<=maxw-minw;i++){
		for(j=0;j<=maxh-minh;j++){
			put_data[i][j]=board_data[i+minw][j+minh];
		}
	}
	for(int i=1;i<blocks;i++){
		block_data[i][0][0]-=minw;
		block_data[i][0][1]-=minh;
	}
	w=maxw-minw+1;
	h=maxh-minh+1;
	//cout << "w is "<< w << "h is " << endl;
	return;
}

void resize2(){
	int i,j;
	int minw=W,maxw=0,minh=H,maxh=0;
	for(int i=0;i<W;i++){
		for(int j=0;j<H;j++){
			put_data[i][j]=0;
		}
	}
	for(i=0;i<W;i++){
		for(j=0;j<H;j++){
			if(line_board[i][j]){
				if(i>maxw)
					maxw=i;
				if(i<minw)
					minw=i;
				if(j>maxh)
					maxh=j;
				if(j<minh)
					minh=j;
			}
		}
	}
	for(i=1;i<=blocks;i++){
		/* block_data[i][0]-=minw; */
		/* block_data[i][1]-=minh; */
	}
	for(i=0;i<=maxw-minw;i++){
		for(j=0;j<=maxh-minh;j++){
			put_data[i][j]=line_board[i+minw][j+minh];
		}
	}
	for(int i=1;i<blocks;i++){
		block_data[i][0][0]-=minw;
		block_data[i][0][1]-=minh;
	}
	w=maxw-minw+1;
	h=maxh-minh+1;
	return;
}

int make_board(){
	int cw=0,ch=0,maxx=0,maxy=0;
	for(int i=1;i<=blocks;i++){
		maxx=0;
		maxy=0;
		for(int j=1;j<=4;j++){
			if(block_data[i][j][0]>maxx){
				maxx=block_data[i][j][0];
			}
			if(block_data[i][j][1]>maxy){
				maxy=block_data[i][j][1];
			}
		}
		cw+=maxx+1;
		ch+=maxy+1;
	}
	W=cw+blocks+1;
	H=ch+blocks+1;
	if(W>72 || H>72){
		return 1;
	}else{
		return 0;
	}
}



void solve(void){
	int limit=0,end=15,check_space=0,check_line=0,flag=0;
	if(make_board()){
		printf("too large\n");
		return;
	}
	//std::cout << "height is " << H <<" width is "<<  W << std::endl;
	init_mino();
	put_mino();
	
	line();
	for(int i=0;i<end;i++){
		check_space=move2space();
		if(check_space){
			/*if(line()==0){
				break;
			}*/
		} 
		check_line=move2line();
		if(check_line){
			if(line()==0){
				break;
			}
		}
		if(check_space==0 && check_line==0){
			//cout << "no more reshape" << endl;
		}
		//resize();
	}
	/*while(move2line()){
		line();
		limit++;
		if(limit==end) break;
	}*/
/* 	while(reshape()){
		line();
		limit++;
		if(limit>=end) break;
	}*/
	//line();
	
	resize();
	return;
}

int solver(void){
	read_data();
	solve();
	/* shape(); */
	//translate();
	if(w>answerw || h>answerh) success=0;
	return success;
}