Christos and the Bricks

Christos is a Civil Engineer. His thesis concerns the material failure in buildings. Specifically, Christos simulates the construction of a wall as a grid of dimensions N ~\times~ M, where each square can either contain a brick (represented by "#") or be empty (represented by "."). At the top of the grid, which can be imagined as the ceiling, there is a layer of concrete, so the bricks located in the top row of the grid are stuck to the ceiling and do not fall. All bricks have concrete on all sides, so those touching bricks from the top row also do not fall, those touching them also do not fall, and so on. We consider that a brick can touch other bricks located in the four neighboring squares of the grid: left, right, top, and bottom.

Christos wants to study the behavior of the wall if some bricks "fail". Specifically, he wants to conduct the following experiment: He selects a set of target bricks and goes and breaks them, one by one. Each time a target brick breaks, a part of the construction may collapse since it will no longer be connected to the rest of the solid piece. Christos wants to know each time a target brick breaks how large the collapsing piece will be, i.e., how many bricks it contains.

Problem

Develop a program in one of the IOI languages (Pascal, C, C++, Java) that reads the initial state of the grid and the set of target bricks and finds the number of bricks that collapse after each break.

Input Files

The input file named brickbreaker.in is a text file. The first line contains two integers ~N~ and ~M~ separated by a single space: the number of rows and columns of the grid, respectively. The next ~N~ lines contain the description of the grid: each of them will contain exactly ~M~ characters, each of which will be "#" or "." depending on whether the corresponding square contains a brick or is empty. The next line contains an integer ~Q~: the number of target bricks Christos will break. Each of the next ~Q~ lines contains two integers ~R_i~ and ~C_i~: the coordinates in the grid (row and column) of the corresponding target brick. The numbering of rows and columns starts from ~1~ (the 1~^\text{st}~ row touches the ceiling, and the ~1~~^\text{st}~ column is the leftmost). Assume that the initial construction of the bricks is stable (no bricks fall before the first break!).

Output Files

The output file named brickbreaker.out is a text file consisting of ~Q~ lines, each containing a single integer: the number of bricks that will collapse when Christos breaks the corresponding target brick.

Note: In the size of the collapsing segment, you should not count the target brick that breaks!

Example of Input - Output Files:

STDIN (brickbreaker.in)

5 5
##.##
#####
..#..
.###.
.#.#.
4
4 2
4 3
2 3
2 5

STDOUT (brickbreaker.out)

1
2
1
0

Explanation: The first target brick is located at position ~(4,\;2)~. When it breaks, the only brick that falls is ~(5,\;2)~, so the answer is ~1~. In the second break, the bricks ~(4,\;4)~ and ~(5,\;4)~ fall, in the third break the brick ~(3,\;3)~ falls, while in the fourth break no bricks will fall.

Constraints:

• For test cases worth 25%, of the total points, it will be:
  ~1 \le N \le 10~, ~1 \le M \le 10~, ~1 \le Q \le N*M~
• For test cases worth 50%, of the total points, it will be:
  ~1 \le N \le 100~, ~1 \le M \le 100~, ~1 \le Q \le N*M~

• For test cases worth 100%, of the total points, it will be:
  ~1 \le N \le 1000~, ~1 \le M \le 1000~, ~1 \le Q \le N*M~

• Formatting: Both in the input and the output, each line terminates with a newline character.
  

• Maximum execution time: 1 sec.
  
• Maximum available memory: 64 MB.