Problem: Falling Block Puzzle

Block drop

You are playing a falling block puzzle. As shown in the figure below, the field of this puzzle has a shape in which cubic cells are arranged in 2 squares x 2 squares in each row, and the rows are infinitely arranged on the top.

<image>

Each cell either has one block that fits snugly in the cell, or nothing. This puzzle proceeds as follows.

1. Some blocks are installed in the initial state.
2. Drop a block that fits in 2 squares x 2 squares x 2 squares from above. However, before dropping, the block can be translated horizontally so that the block does not stick out of the field.
3. When the bottom surface of one of the dropped blocks reaches the bottom of the block or field that has already been placed, all the blocks will stop falling and stop.
4. For each stage, if all 4 squares are filled, the blocks in that stage will disappear, and the blocks above it will fall one by one. Even if there are no blocks in the cell below each block after the fall, it will not fall any further.
5. Return to 2.



Since the blocks placed in the initial state and some lumps to be dropped are given, create a program to find out how many steps can be erased by dropping all the lumps in the order given.

Input

The input consists of 100 or less datasets. Each dataset has the following form.

> (Initial block height H) (Number of lumps to drop N)
> (1st stage in the initial state)
> ...
> (H stage in the initial state)
> (1st drop)
> ...
> (Nth drop)

The first line of each dataset specifies the initial block height H (1 ≤ H ≤ 10) and the number of lumps to drop N (1 ≤ N ≤ 3). Then, the information of each stage in the initial state is given in the following format.

> c11 c12
> c21 c22

cij represents the information of each cell,'#' indicates that a block exists, and'.' Indicates that there is no block. It can be assumed that there are no blocks in all cells or no blocks in all cells for each of the first to H rows. Then, the information of each drop mass is given in the following format.

> b111 b112
> b121 b122
> b211 b212
> b221 b222

As in the initial state format,'#' indicates that a block exists, and'.' Indicates that there is no block. Each block contains at least one block. The blocks contained in the block may be touched only by the corners and sides, and are not necessarily connected by the surface.

Refer to the figure below for the correspondence of the input subscripts of the initial state and block block.

<image>

The end of the input is indicated by a single line of two zeros.

The figure below shows the first data set in the Sample Input shown later. In this dataset, one step can be erased by translating a block of blocks diagonally and then dropping them.

<image>

Output

For each dataset, output on one line how many columns can be erased at the maximum.

Sample Input


1 1

..
..
..
..
..
1 1
. #
..
..
..
..
. #
twenty two

..

..
..
. #

..
..
..
..
..
13
..
..












10 3

..

..

. #

. #
..

..

. #

. #

. #
..
. #
..
..
. #
..
. #
..
..
..
..
..
..
..
..
10 3

. #

..

..
. #
..

. #
. #

. #

..


. #
..
. #
..
..
. #
..
..
..
..
..
..
..
..
. #
0 0

Output for Sample Input


1
0
3
6
6
0





Example

Input

1 1
##
#.
..
..
#.
..
1 1
.#
#.
#.
..
..
.#
2 2
##
#.
##
#.
..
.#
##
#.
#.
..
#.
..
1 3
#.
..
##
##
##
##
##
##
##
##
##
##
##
##
10 3
##
#.
##
#.
##
.#
##
.#
#.
##
#.
##
.#
##
.#
##
.#
#.
.#
#.
#.
.#
#.
.#
#.
..
#.
..
#.
..
#.
..
10 3
##
.#
##
..
##
#.
.#
..
##
.#
.#
##
.#
##
#.
##
##
.#
..
.#
#.
#.
.#
#.
#.
#.
#.
..
..
..
..
.#
0 0


Output

1
0
3
6
6
0

Solution (in CPP):

Solution:
#include<bits/stdc++.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;


enum Type{
	Zero,
	One,
	Tate,
	Yoko,
	Naname,
	Three,
	Four,
};


int H,N;
int ans;
int loc_sum[3][2][2];
bool table[20][2][2],fall[3][2][2][2];
Type type[3];

void copyTable(bool to[20][2][2],bool from[20][2][2]){

	for(int h = 0; h < 20; h++){
		for(int row = 0; row < 2; row++){
			for(int col = 0; col < 2; col++)to[h][row][col] = from[h][row][col];
		}
	}
}

void addBlock(bool to[20][2][2],bool add[2][2][2],int base_h){

	for(int h = 0; h < 2; h++){
		for(int row = 0; row < 2; row++){
			for(int col = 0; col < 2; col++){
				if(add[h][row][col]){
					to[base_h+h][row][col] = add[h][row][col];
				}
			}
		}
	}
}

int deleteBlock(bool tmp_table[20][2][2],int base_h){

	int ret = 0;
	int current_h = base_h,tmp_count;

	for(int i = 0; i < 2; i++){

		tmp_count = 0;
		for(int row = 0; row < 2; row++){
			for(int col = 0; col < 2; col++){
				if(tmp_table[current_h][row][col])tmp_count++;
			}
		}

		if(tmp_count == 4){ //1段下へ平行シフトする

			ret++;

			for(int h = current_h+1; h < 20; h++){
				for(int row = 0; row < 2; row++){
					for(int col = 0; col < 2; col++){
						tmp_table[h-1][row][col] = tmp_table[h][row][col];
						tmp_table[h][row][col] = false;
					}
				}
			}

			//current_hはそのまま

		}else{
			current_h++; //次の高さへ
		}
	}

	return ret;
}

void recursive(int fall_id,int num_delete,bool tmp_table[20][2][2]){

	if(fall_id == N){
		ans = max(ans,num_delete);
		return;
	}

	bool work[2][2][2];
	bool next_tmp_table[20][2][2];
	int base_h; //落下ブロックの底面となる高さ
	bool FLG;
	int next_delete;

	//fall_id番目のブロックの落下計算
	switch(type[fall_id]){
	case Zero:
		recursive(fall_id+1,num_delete,tmp_table);
		break;
	case One:

		//4箇所平行移動する
		for(int to_row = 0; to_row < 2; to_row++){
			for(int to_col = 0; to_col < 2; to_col++){

				//printf("to_row:%d to_col:%d\n",to_row,to_col);

				for(int h = 0; h < 2; h++){
					for(int row = 0; row < 2; row++){
						for(int col = 0; col < 2; col++){
							work[h][row][col] = false;
						}
					}
				}

				for(int h = 0; h < 2; h++){
					for(int row = 0; row < 2; row++){
						for(int col = 0; col < 2; col++){
							if(fall[fall_id][h][row][col]){
								work[h][to_row][to_col] = true; //平行移動
							}
						}
					}
				}

				/*printf("落下\n");
				for(int row = 0; row < 2; row++){
					for(int col = 0; col < 2; col++){
						if(work[0][row][col]){
							printf("#");
						}else{
							printf(".");
						}
					}
					printf("\n");
				}*/

				copyTable(next_tmp_table,tmp_table);
				//落下処理
				FLG = false;
				for(int h = 19; h >= 0; h--){ //落下ブロックの底面となる高さのループ
					if(h > 0){

						for(int row = 0; row < 2; row++){
							for(int col = 0; col < 2; col++){
								if((work[0][row][col] == true && next_tmp_table[h-1][row][col] == true) ||
										(work[1][row][col] == true && next_tmp_table[h][row][col] == true)){ //底面がブロックに接した場合
									FLG = true;
									break;
								}
							}
							if(FLG)break;
						}
						if(FLG){

							//全体に落下ブロックを書き足す
							base_h = h;
							addBlock(next_tmp_table,work,base_h);

							break;
						}

					}else{ //h == 0
						base_h = 0;
						addBlock(next_tmp_table,work,base_h);

						/*printf("addを呼んだあと\n");
						for(int i = 0; i < 2; i++){
							for(int k = 0; k < 2; k++){
								if(next_tmp_table[base_h][i][k]){
									printf("#");
								}else{
									printf(".");
								}
							}
							printf("\n");
						}*/

						break;
					}
				}

				//printf("base_h:%d\n",base_h);

				//消滅&落下処理
				next_delete = num_delete;
				next_delete += deleteBlock(next_tmp_table,base_h);

				//次へ
				recursive(fall_id+1,next_delete,next_tmp_table);
			}
		}
		break;
	case Tate:

		//2箇所平行移動
		for(int to_col = 0; to_col < 2; to_col++){

			for(int h = 0; h < 2; h++){
				for(int row = 0; row < 2; row++){
					for(int col = 0; col < 2; col++){
						work[h][row][col] = false;
					}
				}
			}

			for(int h = 0; h < 2; h++){
				for(int row = 0; row < 2; row++){
					for(int col = 0; col < 2; col++){
						if(fall[fall_id][h][row][col]){
							work[h][row][to_col] = true; //平行移動
						}
					}
				}
			}

			copyTable(next_tmp_table,tmp_table);
			//落下処理
			FLG = false;
			for(int h = 19; h >= 0; h--){ //落下ブロックの底面となる高さのループ
				if(h > 0){

					for(int row = 0; row < 2; row++){
						for(int col = 0; col < 2; col++){
							if((work[0][row][col] == true && next_tmp_table[h-1][row][col] == true) ||
									(work[1][row][col] == true && next_tmp_table[h][row][col] == true)){ //底面がブロックに接した場合
								FLG = true;
								break;
							}
						}
						if(FLG)break;
					}
					if(FLG){

						//全体に落下ブロックを書き足す
						base_h = h;
						addBlock(next_tmp_table,work,base_h);

						break;
					}

				}else{ //h == 0
					base_h = 0;
					addBlock(next_tmp_table,work,base_h);
					break;
				}
			}

			//消滅&落下処理
			next_delete = num_delete;
			next_delete += deleteBlock(next_tmp_table,base_h);

			//次へ
			recursive(fall_id+1,next_delete,next_tmp_table);
		}

		break;
	case Yoko:

		//2箇所平行移動
		for(int to_row = 0; to_row < 2; to_row++){

			for(int h = 0; h < 2; h++){
				for(int row = 0; row < 2; row++){
					for(int col = 0; col < 2; col++){
						work[h][row][col] = false;
					}
				}
			}

			for(int h = 0; h < 2; h++){
				for(int row = 0; row < 2; row++){
					for(int col = 0; col < 2; col++){
						if(fall[fall_id][h][row][col]){
							work[h][to_row][col] = true; //平行移動
						}
					}
				}
			}

			copyTable(next_tmp_table,tmp_table);
			//落下処理
			FLG = false;
			for(int h = 19; h >= 0; h--){ //落下ブロックの底面となる高さのループ
				if(h > 0){

					for(int row = 0; row < 2; row++){
						for(int col = 0; col < 2; col++){
							if((work[0][row][col] == true && next_tmp_table[h-1][row][col] == true) ||
									(work[1][row][col] == true && next_tmp_table[h][row][col] == true)){ //底面がブロックに接した場合
								FLG = true;
								break;
							}
						}
						if(FLG)break;
					}
					if(FLG){

						//全体に落下ブロックを書き足す
						base_h = h;
						addBlock(next_tmp_table,work,base_h);

						break;
					}

				}else{ //h == 0
					base_h = 0;
					addBlock(next_tmp_table,work,base_h);
					break;
				}
			}

			//消滅&落下処理
			next_delete = num_delete;
			next_delete += deleteBlock(next_tmp_table,base_h);

			//次へ
			recursive(fall_id+1,next_delete,next_tmp_table);

		}

		break;
	case Naname:
	case Three:
	case Four:

		copyTable(next_tmp_table,tmp_table);
		//落下処理
		FLG = false;
		for(int h = 19; h >= 0; h--){ //落下ブロックの底面となる高さのループ
			if(h > 0){

				for(int row = 0; row < 2; row++){
					for(int col = 0; col < 2; col++){
						if((fall[fall_id][0][row][col] == true && next_tmp_table[h-1][row][col] == true) ||
								(fall[fall_id][1][row][col] == true && next_tmp_table[h][row][col] == true)){ //底面がブロックに接した場合
							FLG = true;
							break;
						}
					}
					if(FLG)break;
				}
				if(FLG){

					//全体に落下ブロックを書き足す
					base_h = h;
					addBlock(next_tmp_table,fall[fall_id],base_h);

					break;
				}

			}else{ //h == 0
				base_h = 0;
				addBlock(next_tmp_table,fall[fall_id],base_h);
				break;
			}
		}

		//消滅&落下処理
		next_delete = num_delete;
		next_delete += deleteBlock(next_tmp_table,base_h);

		//次へ
		recursive(fall_id+1,next_delete,next_tmp_table);

		break;
	}
}


void func(){

	for(int h = 0; h < 20; h++){
		for(int row = 0; row < 2; row++){
			for(int col = 0; col < 2; col++)table[h][row][col] = false;
		}
	}

	char buf[3];

	//初期データの取得
	for(int h = 0; h < H; h++){
		for(int row = 1; row >= 0; row--){
			scanf("%s",buf);
			for(int col = 0; col < 2; col++){
				if(buf[col] == '#'){
					table[h][row][col] = true;
				}
			}
		}
	}

	for(int id = 0; id < 3; id++){
		for(int h = 0; h < 2; h++){
			for(int row = 0; row < 2; row++){
				for(int col = 0; col < 2; col++)fall[id][h][row][col] = false;
			}
		}
	}
	for(int id = 0; id < 3; id++){
		for(int row = 0; row < 2; row++){
			for(int col = 0; col < 2; col++){
				loc_sum[id][row][col] = 0; //鉛直方向から見下ろした際の、ブロックのある場所の数
			}
		}
	}

	int num,bottom_count;

	for(int id = 0; id < N; id++){ //塊のループ

		//printf("id:%d\n",id);

		bottom_count = 0; //高さ0のブロックの数
		for(int h = 0; h < 2; h++){
			for(int row = 1; row >= 0; row--){
				scanf("%s",buf);
				for(int col = 0; col < 2; col++){
					if(buf[col] == '#'){
						fall[id][h][row][col] = true;
						loc_sum[id][row][col]++;
						if(h == 0)bottom_count++;
					}
				}
			}
		}
		if(bottom_count == 0){ //高さ0にブロックがない場合は、下に平行移動させておく
			//printf("下に平行移動\n");
			for(int row = 0; row < 2; row++){
				for(int col = 0; col < 2; col++){
					fall[id][0][row][col] = fall[id][1][row][col];
					fall[id][1][row][col] = false;
				}
			}
		}


		//ブロック配置のタイプを決定する
		num = 0;
		for(int row = 0; row < 2; row++){
			for(int col = 0; col < 2; col++){
				if(loc_sum[id][row][col] > 0)num++;
			}
		}
		switch(num){
		case 0:
			type[id] = Zero;
			break;
		case 1:
			type[id] = One;
			break;
		case 2:
			if((loc_sum[id][0][0] > 0 && loc_sum[id][0][1] > 0) || (loc_sum[id][1][0] > 0 && loc_sum[id][1][1] > 0)){
				type[id] = Yoko;
			}else if((loc_sum[id][0][0] > 0 && loc_sum[id][1][0] > 0) || (loc_sum[id][0][1] > 0 && loc_sum[id][1][1] > 0)){

				//printf("Tate\n");
				type[id] = Tate;
			}else{
				//printf("Naname\n");
				type[id] = Naname;
			}
			break;
		case 3:
			type[id] = Three;
			break;
		case 4:
			//printf("Four\n");
			type[id] = Four;
			break;
		}
	}

	ans = 0;

	bool first_tmp[20][2][2];

	for(int h = 0; h < 20; h++){
		for(int row = 0; row < 2; row++){
			for(int col = 0; col < 2; col++)first_tmp[h][row][col] = table[h][row][col];
		}
	}

	recursive(0,0,first_tmp);

	printf("%d\n",ans);
}


int main(){

	while(true){
		scanf("%d %d",&H,&N);
		if(H == 0 && N == 0)break;

		func();
	}

	return 0;
}