AT_arc205_a [ARC205A] 2x2 Erasing

縦 $ N $ 行、横 $ N $ 列のグリッドがあります。上から $ r $ 行目、左から $ c $ 列目のマスをマス $ (r,c) $ と表します。各マスは黒か白で塗られており、マス $ (r,c) $ は $ S_{r,c} $ が `#` のとき黒で、 $ S_{r,c} $ が `.` のとき白で塗られています。 このグリッドに対して $ Q $ 個の質問が与えられるので、それぞれについて答えを求めてください。 $ i $ 番目 $ (1\le i\le Q) $ の質問では整数 $ U_i,D_i,L_i,R_i $ が与えられるので、以下の質問の答えを求めてください。 - $ U_i \le r \le D_i $ かつ $ L_i \le c \le R_i $ を **満たさない** マスを全て黒で塗った後、以下の操作を最大で何回できるか求めてください。 - マス $ (r,c),(r,c+1),(r+1,c),(r+1,c+1) $ が全て白で塗られているような整数の組 $ (r,c) $ を選び、これら $ 4 $ つのマスのうち $ 1 $ つを黒で塗る。 各質問について独立に解いてください。言い換えると、各マスの色は質問のたびにはじめの状態にリセットされます。

入力は以下の形式で標準入力から与えられる。 > $ 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 $

$ Q $ 行出力せよ。 $ i $ 行目 $ (1\le i\le Q) $ には、 $ i $ 番目の質問に対する答えを出力せよ。

### Sample Explanation 1 $ 1 $ 番目の質問について考えます。 $ 1\le r\le 3 $ かつ $ 1\le c\le 3 $ を満たさないようなマスを全て黒で塗ると、グリッドは以下のようになります。 ``` ..### ...## #..## ##### ##### ``` このグリッドに対して以下のように $ 2 $ 回操作を行うことができます。 - $ (r,c)=(1,1) $ を選ぶ。マス $ (1,1),(1,2),(2,1),(2,2) $ の中からマス $ (1,2) $ を選び、黒で塗る。 - $ (r,c)=(2,2) $ を選ぶ。マス $ (2,2),(2,3),(3,2),(3,3) $ の中からマス $ (2,2) $ を選び、黒で塗る。 $ 2 $ 回より多く操作をすることはできないので、 $ 1 $ 行目には $ 2 $ を出力してください。 ### Constraints - $ 2\le N\le 500 $ - $ 1\le Q\le 2\times 10^5 $ - $ S_{r,c} $ は `.` または `#` - $ 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 $ は全て整数