human
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.


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.

>...
Using python3 can you solve the prior task?

=====
What is a Python code to find out how many steps can be erased by dropping all the lumps in the order given?
assistant
#Here is Python code to find out how many steps can be erased by dropping all the lumps in the order given.

import sys
readline = sys.stdin.readline
write = sys.stdout.write
def solve():
    H, N = map(int, readline().split())
    if H == N == 0:
        return False
    def get_block():
        s = readline().strip()
        v = (s[0] == '#') + (s[1] == '#')*2
        s = readline().strip()
        v += (s[0] == '#')*4 + (s[1] == '#')*8
        return v
    R = []
    for i in range(H):
        R.append(get_block())
    R.extend([0]*8)
    H += 8
    I = []
    for i in range(N):
        v = get_block(); w = get_block()
        if v == 0:
            v, w = w, 0
        if v & 3 == 0 and w & 3 == 0:
            v >>= 2; w >>= 2
        if v & 5 == 0 and w & 5 == 0:
            v >>= 1; w >>= 1
        I.append((v, w))
    def dfs(i, R0):
        if i == N:
            return 0
        v0, w0 = I[i]
        r = 0
        for k, f in ((0, 0), (1, 5), (2, 3), (3, 0)):
            v = v0 << k; w = w0 << k
            if v >= 16 or w >= 16 or v & f or w & f:
                continue
            h = H-1
            while h and R0[h-1] & v == 0 and R0[h] & w == 0:
                h -= 1
            R = R0[:]
            R[h] |= v; R[h+1] |= w
            c = 0
            if R[h+1] == 15:
                for j in range(h+2, H):
                    R[j-1] = R[j]
                c += 1
            if R[h] == 15:
                for j in range(h+1, H):
                    R[j-1] = R[j]
                c += 1
            r = max(r, dfs(i+1, R) + c)
        return r
    write("%d\n" % dfs(0, R))
    return True
while solve():
    ...