from collections import defaultdict

def solve(X, Y, solution=[]):
    if not X:
        yield list(solution)
    else:
        c = min(X, key=lambda c: len(X[c]))
        for r in list(X[c]):
            solution.append(r)
            cols = select(X, Y, r)
            for s in solve(X, Y, solution):
                yield s
            deselect(X, Y, r, cols)
            solution.pop()


def select(X, Y, r):
    cols = []
    for j in Y[r]:
        for i in X[j]:
            for k in Y[i]:
                if k != j:
                    X[k].discard(i)
        cols.append(X.pop(j))
    return cols


def deselect(X, Y, r, cols):
    for j in reversed(Y[r]):
        X[j] = cols.pop()
        for i in X[j]:
            for k in Y[i]:
                if k != j:
                    X[k].add(i)
                    
sample_tests = [
    [['  0   0 ', '      0 ', '   0  0 ', '      0 ', '0     0 ', '        ', '   00000', '   00   '],
    [[2, 2], [1, 5], [1, 3], [1, 1], [1, 1], [1, 1]]],
    
	[
		[
			'        ',
			' 00 0   ',
			' 00 00  ',
			'  0 00  ',
			'     00 ',
			'  00  0 ',
			'  00  0 ',
			'        '],
			[[1,1],[1,2],[1,2],[1,3],[1,3],[1,3],[2,2]]],
	[
		[
			'            ',
			' 00000      ',
			' 00000      ',
			' 00000   00 ',
			'       000  ',
			'   00  000  ',
			' 0000 00    ',
			' 0000 00    ',
			' 00   000 0 ',
			'   0  000 0 ',
			' 000      0 ',
			'            '],
			[[1,1],[1,1],[1,2],[1,2],[1,2],[1,3],[1,3],[1,4],[1,4],[2,2],[2,2],[2,3],[2,3],[2,5]]],
	[
		[
			'          ',
			'          ',
			'  00  00  ',
			'  00  00  ',
			'          ',
			' 0  00  0 ',
			' 00    00 ',
			'  000000  ',
			'  000000  ',
			'          '],
			[[1,1],[1,1],[1,2],[1,2],[1,2],[1,2],[1,3],[1,3],[1,4],[2,2],[2,2]]]]

def make_constraints(board, rects):
    n, m = len(board), len(board[0])
    M = len(rects)
    
    covered = {}
    areas = [[0 for _ in range(m + 1)]]
   
    num_pos = 0
    for i, row in enumerate(board):
        area_row = [0]
        s = 0
        for j, col in enumerate(row):          
            if board[i][j] == '0':
                p = i * m + j
                covered[p] = num_pos
                num_pos += 1
                s += 1 
            area_row.append(s + areas[i][j + 1])    
        areas.append(area_row)
    print(covered)
    N = len(covered)
    print("N :", N)
    def get_area(i, j, h, w):
        return areas[i + h][w + j] - areas[i][j + w]  - areas[i + h][j] + areas[i][j]
    Y = {}
    constraints = []
    num_rects = 0
    rect_type = {}
    for p in covered:
        i, j = divmod(p, m)
        for idx_rect in range(M):
            h, w = rects[idx_rect]
            if i + h < n and j + w < m:
                area = get_area(i, j, h, w)
                if area == h * w:
                    constraint = [0 for _ in range(N + M)]
                    for u in range(h):
                        for v in range(w):
                            x = (i + u) * m + (j + v)                            
                            constraint[covered[x]] = 1
                    constraint[N + idx_rect] = 1
                    Y["r" + str(num_rects)] = constraint
                    rect_type["r" + str(num_rects)] = idx_rect
                    # print(constraint)
                    constraints.append(constraint)
                    num_rects += 1
            if (h, w) != (w, h):
                if i + w < n and j + h < m:
                    area = get_area(i, j, w, h)
                    if area == h * w:
                        constraint = [0 for _ in range(N + M)]
                        for u in range(w):
                            for v in range(h):
                                x = (i + u) * m + (j + v)
                                constraint[covered[x]] = 1
                        constraint[N + idx_rect] = 1
                        Y["r" + str(num_rects)] = constraint
                        rect_type["r" + str(num_rects)] = idx_rect
                        # print(constraint)
                        constraints.append(constraint)
                        num_rects += 1
    X = {i: set() for i in range(N + M)}
    for k, v in Y.items():
        # print("key ", k, rect_type[k])
        print("v :", v)
    for k, xs in Y.items():
        for i, x in enumerate(xs):
            if x:
                X[i].add(k)
            
    for k, v in X.items():
        print("key ", k)
        print("v :", v)

    ans = solve(X, Y)
    for r in ans:
        print(ans)
        break

 
            
for board, rects in sample_tests[:1]:
    make_constraints(board, rects)