City Lights Queries

You are looking at a square nighttime skyline represented as an $n \times n$ grid. Each cell is one window: a lit window is marked with *, and a dark window is marked with ..

You must answer $q$ queries. Each query gives the top-left corner $(r_1, c_1)$ and the bottom-right corner $(r_2, c_2)$ of a rectangle, and asks how many lit windows are inside that rectangle.

Input

The first line contains two integers $n$ and $q$.

The next $n$ lines each contain a string of length $n$ describing the grid.

Each of the next $q$ lines contains four integers $r_1, c_1, r_2, c_2$ describing an inclusive query rectangle.

Here, $r$ stands for row and $c$ stands for column, so each query is given as row column row column.

Rows and columns are numbered from $1$ to $n$, and the first pair $(r_1, c_1)$ is the top-left corner while the second pair $(r_2, c_2)$ is the bottom-right corner.

Output

For each query, output a single integer: the number of lit windows inside the requested rectangle.

Constraints

• $1 \le n \le 1000$
• $1 \le q \le 2 \cdot 10^5$
• $1 \le r_1 \le r_2 \le n$
• $1 \le c_1 \le c_2 \le n$

Example 1

4 3
.*..
**..
..*.
***.
1 1 2 2
2 2 4 4
3 3 3 3

3
4
1

Example 2

5 3
*....
.*...
..*..
...*.
....*
1 1 5 5
2 1 4 3
1 5 5 5

5
2
1