Problem Description

PAKEN City is a rectangle with dimensions $ H $ meters north-south and $ W $ meters east-west. It is divided into $H \times W$ squares, each of which is 1 meter by 1 meter, and the square at the $ i $-th position from the north and the $ j $-th position from the west is represented as $ (i, j) $.

Some of the squares in Paken City have buildings on them and are impassable, while others are passable. More specifically, $ S_{i, j} $ being # indicates that there is a building and it is impassable, and . indicates that it is passable.

E869120, Santa Claus, has decided to deliver $ Q $ presents to Paken Kingdom.

The $ i $-th present delivery proceeds as follows:

• Initially, a square present with a side length of $ L_i $ meters is placed with its top-left corner at square $ (X_i, Y_i) $.
• After that, the present can be moved. More specifically, the operation of "moving the present exactly 1 meter in one of the four cardinal directions (north, south, east, west) without rotating it, ensuring that it does not overlap with buildings" can be performed any number of times (including zero).

However, moving the present such that any part of it goes outside the boundaries of Paken City is not allowed.

For each present delivery, determine how many possible final positions the present can end up in.

Input Format

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

$ H $ $ W $ $ S_{1, 1} $ $ S_{1, 2} $ $ S_{1, 3} $ $\cdots$ $ S_{1, W} $ $ S_{2, 1} $ $ S_{2, 2} $ $ S_{2, 3} $ $\cdots$ $ S_{2, W} $ $ S_{3, 1} $ $ S_{3, 2} $ $ S_{3, 3} $ $\cdots$ $ S_{3, W} $ : : : $ S_{H, 1} $ $ S_{H, 2} $ $ S_{H, 3} $ $\cdots$ $ S_{H, W} $ $ Q $ $ X_1 $ $ Y_1 $ $ L_1 $ $ X_2 $ $ Y_2 $ $ L_2 $ $ X_3 $ $ Y_3 $ $ L_3 $ : : $ X_Q $ $ Y_Q $ $ L_Q $

Output Format

For each present delivery, output the number of possible final positions for the present, one per line.

Sample Input and Output

Sample Input #1

1 10
.#..##...#
1
1 7 1

Sample Output #1

3

Sample Input #2

6 5
#..#.
..#..
#.#..
..#..
.#..#
.#...
1
3 4 1

Sample Output #2

12

Sample Input #3

8 8
....#...
..#.....
......#.
#.......
...#....
.#......
.....#..
.......#
6
4 5 1
1 6 2
2 5 2
7 1 2
4 6 3
6 3 3

Sample Output #3

56
2
14
6
2
1

Notes/Hints

Constraints

• $1 \leq H \leq 1500$
• $1 \leq W \leq 1500$
• $1 \leq Q \leq 150000$
• $ H, W, Q $ are all integers.
• The initial position of all $ Q $ presents is within Paken City, and none of the $ L_i^2 $ squares have buildings.

Partial Points

This problem is divided into several sub-tasks, and a sub-task is considered solved if all test cases in that sub-task are correct. The score of the submitted source code is the sum of the points of the solved sub-tasks.

1. (13 points) $ H = 1 $, $W \leq 200$, $ Q = 1 $, and the side length of the present $ L_i $ is always $ 1 $.
2. (13 points) $H \leq 200$, $W \leq 200$, $ Q = 1 $, and the side length of the present $ L_i $ is always $ 1 $.
3. (19 points) The side length of the present $ L_i $ is always $ 1 $.
4. (11 points) $H \leq 200$, $W \leq 200$, $ Q = 1 $.
5. (11 points) $H \leq 200$, $W \leq 200$, $Q \leq 1000$.
6. (11 points) $H \leq 200$, $W \leq 200$.
7. (22 points) No additional constraints.

Sample Explanation 1

This input example satisfies the constraints of sub-task 1. The present can be moved to the following 3 positions, including the initial position.

Sample Explanation 2

This input example satisfies the constraints of sub-task 2. The present can be moved to 12 positions.

见题面 Input 部分

见题面 Output 部分