p00132 Jigsaw Puzzle_33278
Brain training puzzle games are popular from children to adults. We decided to make a puzzle game and play with everyone so that we could keep up.

We thought of a jigsaw puzzle game where you pick the pieces you need to fill in the unfinished parts. Figure 1 (a) is an example of a puzzle frame. The part where black is buried and the part where white is unfinished. Pieces that can be used to complete this puzzle are given as shown in Figure 1 (b). From this, select one or more black pieces that can fill the white part of the frame. For example, the combination shown in Selection Example 1 in Fig. 2 is correct. On the other hand, the combination like selection example 2 will not complete the puzzle, so it will be incorrect. It is also incorrect if the selected piece is left over. In this way, the player clears the game by selecting the appropriate piece.

Therefore, we decided to develop a judgment program to be used in this puzzle game. Create a program that inputs a combination of unfinished puzzles, piece candidates, and pieces selected by the player, and outputs YES if the player can select the appropriate piece, and NO otherwise. Please give me.

In this problem, the puzzle frame is represented by an array of H x W, and the unfinished part is given by. (Half-width period) and the completed part is given by # (half-width sharp). The maximum size of the puzzle frame is 20 x 20. In addition, each piece is represented by an array of h × w, and the parts that make up the piece are given by # and the parts that are not are given by. Each given piece can be rotated 90 degrees, 180 degrees, and 270 degrees from its original state. Also, the maximum size of each piece is 20 x 20, and the maximum number of pieces n given is 10.

<image>



Input

Given multiple datasets. Each dataset is given in the following format:


H W
g1,1 g1,2 ... g1, W
g2,1 g2,2 ... g2, W
::
gH, 1gH, 2 ... gH, W
n
h1 w1
c11,1 c11,2 ... c11, w1
c12,1 c12,2 ... c12, w1
::
c1h1,1c1h1,2 ... c1h1, w1
::
::
hn wn
cn1,1 cn1,2 ... cn1, wn
cn2,1 cn2,2 ... cn2, wn
::
cnhn, 1cnhn, 2 ... cnhn, wn
p
k1 t1 t2 ... tk1
k2 t1 t2 ... tk2
::
kp t1 t2 ... tkp


The first line gives the puzzle frame sizes H (vertical) and W (horizontal). The second line is given the H line, which consists of the letters gi, j (. Or #) and represents the board of the puzzle.

This is followed by information on the number of pieces n, n pieces. The information for each piece is given the size of the array of l-th pieces, hl (vertical) and wl (horizontal), and the array of l-th pieces. A one-line wl character string consisting of the characters cli, j (. Or #) is given as an array of l-th pieces on the hl line.

It is then given the number of players p, the number of selected pieces for the i-th player ki, and the number tj for the selected pieces.

Input ends with a line containing two 0s. The number of datasets does not exceed 10.

Output

For each dataset, print the correctness YES or NO of the piece selected by the i-th player on line i.

Examples

Input

14 20
####################
###.............####
####..........######
#######.....########
########.....#######
###..###......######
###..####......#####
#########......#####
###########.....####
############.....###
###.########......##
###.#######...###.##
##...###....#####.##
####################
10
12 15
#############..
.##########....
....#####......
.....#####.....
.....######....
......######...
......######...
........#####..
.........#####.
.........######
........###...#
.....####.....#
3 3
#..
###
#..
2 2
##
##
4 10
....#####.
....######
...###...#
####.....#
6 5
....#
..###
#####
##.##
#..##
#..#.
6 4
...#
.###
####
##.#
##.#
#...
2 6
######
.#####
2 7
..#####
#######
2 13
#############
.##########..
6 9
#####....
.######..
.######..
..######.
...#####.
....#####
8
3 1 2 3
4 1 2 3 4
7 2 3 4 5 6 7 8
5 2 3 10 7 8
6 2 3 9 5 6 4
8 2 3 4 6 9 5 4 10
4 4 5 6 9
5 10 2 3 4 9
0 0


Output

YES
NO
YES
NO
YES
NO
NO
YES


Input

14 20

.............####
..........######
.....########
.....#######
..###......######
..####......#####
......#####
.....####
.....###
.########......##
.#######...###.##
...###....#####.##

10
12 15
..
.##########....
....#####......
.....#####.....
.....######....
......######...
......######...
........#####..
.........#####.
.........######
........###...#
.....####.....#
3 3
..

..
2 2


4 10
....#####.
....######
...###...#
.....#
6 5
....#
..###

.##
..##
..#.
6 4
...#
.###

.#
.#
...
2 6

.#####
2 7
..#####

2 13

.##########..
6 9
....
.######..
.######..
..######.
...#####.
....#####
8
3 1 2 3
4 1 2 3 4
7 2 3 4 5 6 7 8
5 2 3 10 7 8
6 2 3 9 5 6 4
8 2 3 4 6 9 5 4 10
4 4 5 6 9
5 10 2 3 4 9
0 0


Output

YES
NO
YES
NO
YES
NO
NO
YES
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

//Jigsaw Puzzle
public class Main{

	int h, w, n;
	int[] puzzle;
	List<R>[] piece;
	boolean[] res;
	
	class R{
		int H, W;
		int[] p;
		String str;
		public R(int h, int w, char[][] m) {
			H = h;
			W = w;
			p = new int[H];
			str = "";
			for(int i=0;i<H;i++)for(int j=0;j<W;j++){
				p[i] = (p[i]<<1) + (m[i][j]=='#'?1:0);
				str+=m[i][j];
			}
		}
		boolean eq(R r){
			if(H!=r.H || W!=r.W)return false;
			return str.equals(r.str);
		}
		void print(){
			for(int i=0;i<H;i++){
				for(int j=0;j<W;j++)System.out.print(str.charAt(i*W+j));
				System.out.println();
			}
		}
	}
	
	char[][] rot(char[][] a){
		int H = a.length, W = a[0].length;
		char[][] res = new char[W][H];
		for(int i=0;i<H;i++)for(int j=0;j<W;j++)res[W-j-1][i] = a[i][j];
		return res;
	}
	
	void print(){
		for(int i=0;i<h;i++){
			for(int j=w-1;j>=0;j--)System.out.print(((puzzle[i]>>j)&1)==0?'#':'.');
			System.out.println();
		}
	}
	
	void dfs(int i, int j, int U, int idx){
//		System.out.printf("(%d, %d) U:%d idx:%d\n", i, j, U, idx);
		if(j==w){
			dfs(i+1, 0, U, 0); return;
		}
		if(i==h){
//			System.out.println("U:"+U);
			res[U] = true; return;
		}
		for(int u=idx;u<n;u++)if(((U>>u)&1)==0){
			for(R r:piece[u]){
				if(h < i+r.H || w < j+r.W)continue;
				boolean ok = true;
				for(int y=0;y<r.H;y++)if( (puzzle[i+y] & (r.p[y]<<(w-r.W-j))) != (r.p[y]<<(w-r.W-j))){
					ok = false; break;
				}
				if(!ok)continue;
//				System.out.printf("(%d, %d) U:%d\n", i, j, U);
//				System.out.println("PIECE NO:"+(u+1));
//				r.print();
//				System.out.println("BEFORE:");
//				print();
				for(int y=0;y<r.H;y++){
					puzzle[i+y] -= (r.p[y]<<(w-r.W-j));
				}
//				System.out.println("AFTER:");
//				print();
				if(((puzzle[i]>>(w-j-1))&1)==0){
//					System.out.println("MOGURU");
					dfs(i, j, U + (1<<u), u+1);
				}
//				System.out.println("MODOSU: BEFORE");
//				print();
				for(int y=0;y<r.H;y++){
					puzzle[i+y] |= (r.p[y]<<(w-r.W-j));
				}
//				System.out.println("MODOSU: AFTER");
//				print();
				
			}
		}
		if(((puzzle[i]>>(w-j-1))&1)==0)
			dfs(i, j+1, U, 0);
	}
	
	@SuppressWarnings("unchecked")
	void run(){
		Scanner sc = new Scanner(System.in);
		piece = new List[10];
		for(;;){
			h = sc.nextInt(); w = sc.nextInt();
			if((h|w)==0)break;
			puzzle = new int[h];
			for(int i=0;i<h;i++){
				char[] s = sc.next().toCharArray();
				for(char c:s)puzzle[i] = (puzzle[i]<<1) + (c=='#'?0:1);
			}
			n = sc.nextInt();
			for(int i=0;i<n;i++){
				piece[i] = new ArrayList<R>();
				int H = sc.nextInt(), W = sc.nextInt();
				char[][] m = new char[H][];
				for(int j=0;j<H;j++)m[j]=sc.next().toCharArray();
				piece[i].add(new R(H, W, m));
				for(int k=0;k<3;k++){
					m = rot(m);
					int t = H;
					H = W; W = t;
					piece[i].add(new R(H, W, m));
				}
				for(int j=0;j<piece[i].size();j++)for(int k=j+1;k<piece[i].size();k++)if(piece[i].get(j).eq(piece[i].get(k))){
					piece[i].remove(k--);
				}
//				for(R r:piece[i]){
//					r.print();
//					System.out.println();
//				}
			}
			res = new boolean[1<<n];
			dfs(0, 0, 0, 0);
			int Q = sc.nextInt();
			while(Q--!=0){
				int k = sc.nextInt(), S = 0;
				while(k--!=0)S+=(1<<(sc.nextInt()-1));
				System.out.println(res[S]?"YES":"NO");
			}
		}
	}
	
	public static void main(String[] args) {
		new Main().run();
	}
}