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

Input

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

Output

3
4
1

Example 2

Input

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

Output

5
2
1