Problem Statement

There is a grid with $N$ rows and $N$ columns. Let $(r,c)$ denote the cell at the $r$-th row from the top and $c$-th column from the left. Each cell is colored black or white. Cell $(r,c)$ is colored black when $S_{r,c}$ is #, and white when $S_{r,c}$ is ..

You are given $Q$ questions about this grid, so answer each of them. In the $i$-th question $(1\le i\le Q)$, integers $U_i,D_i,L_i,R_i$ are given, so find the answer to the following question.

• After coloring all cells that do not satisfy $U_i \le r \le D_i$ and $L_i \le c \le R_i$ black, find the maximum number of times you can perform the following operation.
• Choose a pair of integers $(r,c)$ such that cells $(r,c),(r,c+1),(r+1,c),(r+1,c+1)$ are all colored white, and color one of these four cells black.

Solve each question independently. In other words, the color of each cell is reset to the initial state for each question.

Constraints

• $2\le N\le 500$
• $1\le Q\le 2\times 10^5$
• $S_{r,c}$ is . or #.
• $1\le U_i < D_i \le N$
• $1\le L_i < R_i \le N$
• $N,Q,U_i,D_i,L_i,R_i$ are all integers.

Input

The input is given from Standard Input in the following format:

N Q
S_{1,1}S_{1,2}\ldots S_{1,N}
S_{2,1}S_{2,2}\ldots S_{2,N}
\vdots
S_{N,1}S_{N,2}\ldots S_{N,N}
U_1 D_1 L_1 R_1
U_2 D_2 L_2 R_2
\vdots
U_Q D_Q L_Q R_Q

Output

Output $Q$ lines.

The $i$-th line $(1\le i\le Q)$ should contain the answer to the $i$-th question.