Logo

Time limit1sMemory limit128 MB

Summary

Given up to five polyomino patch shapes (each a subset of a 3x3 grid, flippable and rotatable) and up to three grid designs up to 55x5, decide if each design can be tiled exactly by non-overlapping patches and find the minimum patch count, or report NIE.

Level: Hard10 of 10
Topics: Dynamic programming, Bit manipulation, Backtracking, Implementation
Solved: No attempts yet

Problem

A company logo is designed on a rectangular grid of unit squares by blackening some of them. A sign is built by gluing gold patches onto a rectangular background so that the resulting golden figure has exactly the shape of the logo (the set of black squares). Patches may be rotated and flipped (used either side up), but they may not overlap. Each unit square of the design corresponds to one gold square of size $1\,\text{m} \times 1\,\text{m}$ .

The manufacturer uses patches of a few shapes. Each patch is a single connected piece of unit squares (you can move between any two of its squares through squares that share an edge), stamped from a $3 \times 3$ matrix by cutting out some of the nine squares.

For each order (design), decide whether it can be built using only the available patch shapes, and if so find the minimum number of patches required.

Write a program that:

reads the patch shapes used by the manufacturer,
reads the sign designs,
for each design decides whether it is feasible and, if so, computes the minimum number of patches needed,
writes the results to standard output.

Input

The first line contains an integer $n$ ( $1 \le n \le 5$ ), the number of patch shapes used.

Then follow $n$ shape descriptions. Each shape spans 3 lines of 3 characters each. # means the square belongs to the patch, . means the square is cut out of the matrix.

Then a line contains the number of designs $m$ ( $1 \le m \le 3$ ).

Then follow $m$ design descriptions. Each design begins with two integers $x$ , $y$ ( $1 \le x \le 55$ , $1 \le y \le 5$ ), the width and height of the sign in meters. Each of the next $y$ lines contains $x$ characters. # means the square must be gold, . means it must stay empty.

Consecutive blocks in the input (the count lines, each shape description, each design description) are separated by a single blank line.

Output

Print exactly $m$ lines. On the $i$ -th line print the minimum number of patches needed to produce the $i$ -th design, or the single word NIE if the design cannot be built.

Examples5

Example 1

Input

2

###
..#
...

...
#..
...

1

12 4
###..#...###
#.#..#...#.#
###..#...###
#.#..###.#.#

Expected output

Example 2

Input

1

#..
...
...

3

1 1
#

3 2
###
#.#

2 2
##
.#

Expected output

1
5
3

Example 3

Input

1

##.
...
...

3

2 1
##

3 1
###

2 2
##
##

Expected output

1
NIE
2

Example 4

Input

2

#..
...
...

##.
...
...

3

3 1
###

1 1
#

4 1
####

Expected output

2
1
2

Example 5

Input

1

###
..#
...

3

3 2
###
..#

1 1
#

3 2
###
#..

Expected output

1
NIE
1