Problem Statement

There is a sheet of grid paper with $H$ rows and $W$ columns.
The cell in row $i$, column $j$ of the grid is denoted by $(i, j)$. The top-left cell is $(1, 1)$; row numbers increase downward and column numbers increase to the right.
Also, the rectangular region whose top-left cell is $(a, b)$ and whose bottom-right cell is $(c, d)$ is denoted by $\{(a, b), (c, d)\}$.

Each cell of the grid has the character 'c' or 'w' written on it.
C-san wants to know how many chihuahuas are contained in certain rectangular regions of this grid.
According to C-san, the number of chihuahuas in a rectangular region $R = \{(a, b), (c, d) \}$ equals the number of tuples of cells $((i_1, j_1), (i_2, j_2), (i_3, j_3))$ satisfying the following conditions.

• $(i_1, j_1), (i_2, j_2), (i_3, j_3)$ are all cells inside the rectangular region $R$. That is, $a \leq i_1, i_2, i_3 \leq c$ and $b \leq j_1, j_2, j_3 \leq d$.
• $(i_1, j_1), (i_2, j_2), (i_3, j_3)$ are all distinct cells, lined up in this order in one of the directions up, down, left, or right. However, the cells do not have to be adjacent. That is, one of the following holds.
  • $i_1 = i_2 = i_3$ and $j_1 < j_2 < j_3$
  • $i_1 = i_2 = i_3$ and $j_1 > j_2 > j_3$
  • $i_1 < i_2 < i_3$ and $j_1 = j_2 = j_3$
  • $i_1 > i_2 > i_3$ and $j_1 = j_2 = j_3$
• The cell $(i_1, j_1)$ has the character 'c' written on it, and the cells $(i_2, j_2), (i_3, j_3)$ have the character 'w' written on them.

Input

$H$ $W$
$s_1$
$s_2$
...
$s_H$
$Q$
$a_1$ $b_1$ $c_1$ $d_1$
$a_2$ $b_2$ $c_2$ $d_2$
...
$a_Q$ $b_Q$ $c_Q$ $d_Q$

• The first line contains the number of rows $H$ and the number of columns $W$ $(1 \leq H \leq 500, 1 \leq W \leq 500)$ of the grid as space-separated integers.
• From the second line to line $H + 1$, the information of the cells of the grid is given as one string per line.
• The string $s_i$ on line $i + 1$ consists of $W$ characters, and the $j$-th character of $s_i$ represents the character written on cell $(i, j)$.
• $s_i$ contains no characters other than 'c' and 'w'.
• Line $H + 2$ contains the number of queries $Q$ $(1 \leq Q \leq 10000)$.
• From line $H + 3$ to line $H + Q + 2$, the information of the $i$-th query $a_i, b_i, c_i, d_i$ $(1 \leq i \leq Q, 1 \leq a_i, c_i \leq H, 1 \leq b_i, d_i \leq W, a_i \leq c_i, b_i \leq d_i)$ is given.
• $a_i, b_i, c_i, d_i$ indicate that the rectangular region asked about in the $i$-th query has top-left cell $(a_i, b_i)$ and bottom-right cell $(c_i, d_i)$.

Output

The output consists of $Q$ lines.
On line $i$, print the answer to the $i$-th query on a single line.
Note that the answer may not fit in a 32-bit integer type.
Also, do not forget the trailing newline.

Sample

5 5
cwcww
wwwcw
wcwcw
ccwcc
wwwww
4
1 1 3 3
1 2 4 5
4 1 4 5
5 1 5 1

3
11
0
0