Description

Puzzle is a very annoying to find the next piece to fill in.
As a CS student, you decides to help peoples to solve this problem by your programimg skill.

There’s a n × m incomplete puzzle board.
The empty fields are marked as o while the filled ones are #.

Let’s define space = colletion of the connected empty field.
That is, there’re one space(3x3) on the Board 1, and two spaces(1x3) on the Board 2.

// Board 1, Board 2
   #####    #####
   #ooo#    #ooo#
   #ooo#    #####
   #ooo#    #ooo#
   #####    #####

Now, there’re T pieces of puzzle to check whether each of them is able to be put into the space on the board or not.
Because the orientation of piece is important in painting puzzle, it’s no need to check the rotated piece can be put into board or not.
The shapes of piece is also described by o, #.
The following examples representing the piece with rectangle, cross, mountant shape.

###    o#o    oo#oo
###    ###    #o#o#
       o#o    #####

Your task is to answer these pieces can be put in to the given board or not.

Type of shape

1. rectangle: the shape is a filled rectangle.

#    ##    ##    ####
           ##    ####
           ##    ####

2. symmetric: the shape is the same after any rotation.

###    oo#o    oo#oo
#o#    ###o    oo#oo
###    o###    #####
       o#oo    oo#oo
               oo#oo

3. irregular: the shape has no rule.

##o    ####    oo#oo
#oo    #o#o    #o#o#
###    #ooo    #####

 

Hint for Testcases

Testcases	Number of space	Shape of space	Shape of pieces
1	1	Sample	Sample
2	1	rectangle	rectangle (1x1)
3	1	rectangle	rectangle
4	1	symmetric	symmetric
5	no restriction	irregular	irregular

 

Input

There’re two integers n, m on the first line.
The following n lines contains m charactors, representing the n×m incompleted board.
There’s an integer T on the next line, denoting the number of pieces.

And then are T pieces of puzzle.
For each piece, there’re two integers ri,ci, denoting the size of pieces.
The next ri lines with ci charactors are the shape of i^th piece.

It’s guaranteed that:

• 1 ≤ n, m ≤ 50
• 1 ≤ T ≤ 100
• 1 ≤ ri, ci ≤ 4
• All pieces only have one connected component.
• There’s no redudant rows or columns in pieces.
  In the other word, there’s at least one # for the first row, last row, first column, and last columns.
  That is, the following pieces will not happen in the Input

2 3 // 2 connected component
#o#
#o#
#o#
2 4 // 4 connected component
#o#o
o#o#
3 3 // 3-rd row is redudant
###
o#o
ooo
2 2 // 1-st row, 1-st column are redudant
oo
o#

Output

There’re T lines for output.
Print “Yes” on the i^th line if the i^th piece can be put in to board.
Otherwise, “No” on the i^th line.

Remember ‘\n’ on the end of each lines.

Sample Input  Download

Sample Output  Download

Tags

Add Tag

Discuss