A. Flips
time limit per test
5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a $$$n \times m$$$ board with white or black cells. Each second the board is going to change. For each $$$2 \times 2$$$ square on the previous board, if it doesn't contain two adjacent cells of the same color, all four cells will have their color flipped on the next board. If a cell didn't belong to any of such $$$2 \times 2$$$ squares, its color stays the same. The initial board is in time $$$0$$$. Your task is to answer $$$q$$$ queries. Each query contains one number $$$t$$$ — calculate the number of black cells after $$$t$$$ seconds.

Input

The first line of input contains three integers $$$n$$$, $$$m$$$ and $$$q$$$ ($$$1 \leq n, m \leq 2\,000$$$, $$$1 \leq q \leq 200\,000$$$). The next $$$n$$$ lines contain a description of the board. The $$$i$$$-th of these lines contains a string of length $$$m$$$ representing the $$$i$$$-th row. If $$$j$$$-th letter of the string is '#', then cell (i, j) is black. If it's '.' then it's white. The next $$$q$$$ lines contain descriptions of the following queries. In each line there is one integer $$$t$$$ ($$$1 \leq t \leq 10^9$$$) described above.

Output

Output $$$q$$$ lines. In $$$i$$$-th of these lines print the answer to the $$$i$$$-th query from input.

Example
Input
3 4 2
#.#.
##.#
.#.#
1
10
Output
7
6