{"problem":{"name":"2x2 Erasing","description":{"content":"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 colore","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"arc205_a"},"statements":[{"statement_type":"Markdown","content":"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 `.`.\nYou 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.\n\n*   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.\n    *   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.\n\nSolve each question independently. In other words, the color of each cell is reset to the initial state for each question.\n\n## Constraints\n\n*   $2\\le N\\le 500$\n*   $1\\le Q\\le 2\\times 10^5$\n*   $S_{r,c}$ is `.` or `#`.\n*   $1\\le U_i < D_i \\le N$\n*   $1\\le L_i < R_i \\le N$\n*   $N,Q,U_i,D_i,L_i,R_i$ are all integers.\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$N$ $Q$\n$S_{1,1}S_{1,2}\\ldots S_{1,N}$\n$S_{2,1}S_{2,2}\\ldots S_{2,N}$\n$\\vdots$\n$S_{N,1}S_{N,2}\\ldots S_{N,N}$\n$U_1$ $D_1$ $L_1$ $R_1$\n$U_2$ $D_2$ $L_2$ $R_2$\n$\\vdots$\n$U_Q$ $D_Q$ $L_Q$ $R_Q$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"arc205_a","tags":[],"sample_group":[["5 4\n..#.#\n.....\n#....\n...#.\n.#...\n1 3 1 3\n3 5 3 5\n2 3 1 4\n1 5 1 5","2\n0\n2\n5\n\nConsider the first question.\nAfter coloring all cells that do not satisfy $1\\le r\\le 3$ and $1\\le c\\le 3$ black, the grid becomes as follows.\n\n..###\n...##\n#..##\n#####\n#####\n\nYou can perform the operation twice on this grid as follows.\n\n*   Choose $(r,c)=(1,1)$. Among cells $(1,1),(1,2),(2,1),(2,2)$, choose cell $(1,2)$ and color it black.\n*   Choose $(r,c)=(2,2)$. Among cells $(2,2),(2,3),(3,2),(3,3)$, choose cell $(2,2)$ and color it black.\n\nYou cannot perform the operation more than twice, so output $2$ on the first line."],["7 6\n#.#....\n.....#.\n.......\n.#..#.#\n#....#.\n.......\n....##.\n1 3 2 7\n4 6 1 6\n6 7 2 7\n3 5 4 6\n1 6 2 4\n1 7 1 7","4\n4\n2\n0\n6\n13"]],"created_at":"2026-03-03 11:01:14"}}