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 ~(y_1, x_1)~ and the bottom-right corner ~(y_2, x_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 ~y_1, x_1, y_2, x_2~ describing an inclusive query rectangle.

Rows and columns are numbered from ~1~ to ~n~.

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 y_1 \le y_2 \le n~
• ~1 \le x_1 \le x_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