AT_arc205_a [ARC205A] 2x2 Erasing

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.

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 $ Q $ lines. The $ i $ -th line $ (1\le i\le Q) $ should contain the answer to the $ i $ -th question.

### Sample Explanation 1 Consider the first question. After coloring all cells that do not satisfy $ 1\le r\le 3 $ and $ 1\le c\le 3 $ black, the grid becomes as follows. ``` ..### ...## #..## ##### ##### ``` You can perform the operation twice on this grid as follows. - Choose $ (r,c)=(1,1) $ . Among cells $ (1,1),(1,2),(2,1),(2,2) $ , choose cell $ (1,2) $ and color it black. - Choose $ (r,c)=(2,2) $ . Among cells $ (2,2),(2,3),(3,2),(3,3) $ , choose cell $ (2,2) $ and color it black. You cannot perform the operation more than twice, so output $ 2 $ on the first line. ### 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.