Speedy Turtle

Pafnutiy and his friends love board games that demand fast mental arithmetic. Their favorite at evening gatherings in the NUOP (Unknown University of Olympiad Programming) classrooms is called Speedy Turtle. The game set contains the following parts.

• A grid of N rows and M columns. Each cell is either free or blocked for movement.
• Q game cards. Each card describes three sets: a set A of starting cells, a set B of cells that get additionally blocked, and a set C of ending cells. A, B, and C are non-empty, pairwise disjoint, and consist only of free cells.
• A small turtle token.

The players draw the cards one by one. For each card, count the good triples of cells (a_i, b_j, c_k) with a_i in A, b_j in B, and c_k in C. A triple is good if the turtle can move from the starting cell a_i to the ending cell c_k without visiting the cell b_j. The turtle must follow these rules:

1. It may only move down and to the right, staying inside the grid.
2. It may not stand on a blocked cell.
3. The cell b_j is also blocked for movement.

The first line contains two integers N and M ($1 \le N, M \le 150$), the number of rows and columns of the grid. Then N lines follow, each with M characters describing the grid from top to bottom and left to right. The character '.' is a free cell and '#' is a blocked cell. Rows and columns are numbered from 1.

The next line contains the integer Q ($1 \le Q \le 10^5$), the number of cards. Each card is a block of three lines describing the sets A, B, and C in that order. Each line starts with the size of the set, followed by the cells as pairs of row and column numbers. All cells within one description are distinct.

All sets are non-empty, all cells in all sets are free, and no cell belongs to more than one set of the same card.

The total size of all sets over all cards does not exceed $300000$: $\sum (|A_i| + |B_i| + |C_i|) \le 300000$. The total number of triples over all cards does not exceed $2 \cdot 10^7$: $\sum |A_i| \cdot |B_i| \cdot |C_i| \le 2 \cdot 10^7$.

Print exactly Q numbers, one per line. The i-th number is the answer for the i-th card in the input order.

In every triple of the first card, the turtle starts at the top left corner and ends at the bottom right corner. This is possible only when b_j is the cell at row 2, column 1. So the only good triple is $(1,1)$, $(2,1)$, $(5,6)$.

The good triples of the second card are $(1,2)$, $(3,1)$, $(5,6)$; $(2,1)$, $(3,1)$, $(5,6)$; and $(2,1)$, $(3,1)$, $(5,1)$.