Problem Description

In Tenkaichi Kingdom, a certain puzzle is extremely popular. In this puzzle, a polygon formed by connecting $1 \times 1$ square blocks by their edges is called a piece, and the goal is to tile the given pieces into a rectangle of size $H \times W$ to complete the puzzle.

Takahashi has completed this puzzle!

However, he became curious about how much damage he could do to the completed puzzle with just one finger. He plans to press down on the block at the $x$-th column from the left and the $y$-th row from the top with his index finger and drag it downwards. When a piece contains a block that is dragged down, all blocks of that piece will be dragged down as well.

Additionally, blocks whose bottom edges are connected to the dragged blocks will also be dragged down together.

Takahashi wants to know in advance how many $1 \times 1$ square blocks will move when he performs this dragging action.

You are given $Q$ candidate positions for the block that Takahashi will drag with his index finger. For each candidate, output the number of blocks that will likely be dragged down as a result of Takahashi's action.

Input Format

The input is given from the standard input in the following format:

$ H $ $ W $ $ c_{1,1} $ $ c_{1,2} $ ... $ c_{1,W} $ $ c_{2,1} $ $ c_{2,2} $ ... $ c_{2,W} $ : $ c_{H,1} $ $ c_{H,2} $ ... $ c_{H,W} $ $ Q $ $ x_1 $ $ y_1 $ $ x_2 $ $ y_2 $ : $ x_Q $ $ y_Q $

• The first line contains two integers representing the number of blocks vertically $H\ (1\ ≦\ H\ ≦\ 20000)$ and horizontally $W\ (1\ ≦\ W\ ≦\ 16)$ separated by a space.
• The next $ H $ lines provide information about the puzzle. The $i(1\ ≦\ i\ ≦\ H)$-th line contains a string of $ W $ characters. The $j(1\ ≦\ j\ ≦\ W)$-th character $ c_{i,j} $ represents the type of block at the $ i $-th row from the top and the $ j $-th column from the left. When vertically or horizontally adjacent blocks are of the same type, they belong to the same piece. Note that $ c_{i,j} $ is always an uppercase alphabet.
• The $H\ +\ 2$-th line contains an integer $Q\ (1\ ≦\ Q\ ≦\ 100000)$ representing the number of candidate positions for dragging.
• The next $ Q $ lines provide information about the candidate block positions for dragging. The $i(1\ ≦\ i\ ≦\ Q)$-th line contains two integers $x_i,\ y_i\ (1\ ≦\ x_i\ ≦\ W,\ 1\ ≦\ y_i\ ≦\ H)$ separated by a space, representing the position of the $ i $-th candidate block.

Output Format

For each of Takahashi's dragging locations, output the number of blocks that can be dragged in $ Q $ lines. Ensure to include a newline at the end of the output.

Sample Input and Output

Sample Input #1

5 3
AAB
ABB
CDE
FFH
GHH
2
1 1
2 3

Sample Output #1

15
7

Sample Input #2

2 2
AB
BA
2
1 1
2 1

Sample Output #2

2
2

Sample Input #3

5 5
AABAA
ACDEA
AFGHA
AIJKA
AAAAA
1
3 1

Sample Output #3

25

Notes/Hints

Partial Points

If you correctly solve all test cases where $ Q=1 $, you will be awarded 30 points as partial credit.

Sample Explanation 1

Let $(x,y)$ denote the block at the $x$-th column from the left and the $y$-th row from the top. The block at $(1,1)$ is A. Dragging A down will drag all blocks. The block at $(2,3)$ is D. Dragging D down will drag D, F, G, and H.

Sample Explanation 2

Note that even if the same alphabet is used, it could still be a different piece.

Sample Explanation 3

Dragging the block B will drag all blocks.

见题面 Input 部分

见题面 Output 部分