{"problem":{"name":"Nuske vs Phantom Thnook","description":{"content":"Nuske has a grid with $N$ rows and $M$ columns of squares. The rows are numbered $1$ through $N$ from top to bottom, and the columns are numbered $1$ through $M$ from left to right. Each square in the","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":4000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"agc015_c"},"statements":[{"statement_type":"Markdown","content":"Nuske has a grid with $N$ rows and $M$ columns of squares. The rows are numbered $1$ through $N$ from top to bottom, and the columns are numbered $1$ through $M$ from left to right. Each square in the grid is painted in either blue or white. If $S_{i,j}$ is $1$, the square at the $i$\\-th row and $j$\\-th column is blue; if $S_{i,j}$ is $0$, the square is white. For every pair of two blue square $a$ and $b$, there is at most one path that starts from $a$, repeatedly proceeds to an adjacent (side by side) blue square and finally reaches $b$, without traversing the same square more than once.\nPhantom Thnook, Nuske's eternal rival, gives $Q$ queries to Nuske. The $i$\\-th query consists of four integers $x_{i,1}$, $y_{i,1}$, $x_{i,2}$ and $y_{i,2}$ and asks him the following: when the rectangular region of the grid bounded by (and including) the $x_{i,1}$\\-th row, $x_{i,2}$\\-th row, $y_{i,1}$\\-th column and $y_{i,2}$\\-th column is cut out, how many connected components consisting of blue squares there are in the region?\nProcess all the queries.\n\n## Constraints\n\n*   $1 ≤ N,M ≤ 2000$\n*   $1 ≤ Q ≤ 200000$\n*   $S_{i,j}$ is either $0$ or $1$.\n*   $S_{i,j}$ satisfies the condition explained in the statement.\n*   $1 ≤ x_{i,1} ≤ x_{i,2} ≤ N(1 ≤ i ≤ Q)$\n*   $1 ≤ y_{i,1} ≤ y_{i,2} ≤ M(1 ≤ i ≤ Q)$\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$N$ $M$ $Q$\n$S_{1,1}$..$S_{1,M}$\n:\n$S_{N,1}$..$S_{N,M}$\n$x_{1,1}$ $y_{i,1}$ $x_{i,2}$ $y_{i,2}$\n:\n$x_{Q,1}$ $y_{Q,1}$ $x_{Q,2}$ $y_{Q,2}$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"agc015_c","tags":[],"sample_group":[["3 4 4\n1101\n0110\n1101\n1 1 3 4\n1 1 3 1\n2 2 3 4\n1 2 2 4","3\n2\n2\n2\n\n![image](https://atcoder.jp/img/agc015/7aa4a2252f50a19fc18e0cec01368a2a.png)\nIn the first query, the whole grid is specified. There are three components consisting of blue squares, and thus $3$ should be printed.\nIn the second query, the region within the red frame is specified. There are two components consisting of blue squares, and thus $2$ should be printed. Note that squares that belong to the same component in the original grid may belong to different components."],["5 5 6\n11010\n01110\n10101\n11101\n01010\n1 1 5 5\n1 2 4 5\n2 3 3 4\n3 3 3 3\n3 1 3 5\n1 1 3 4","3\n2\n1\n1\n3\n2"]],"created_at":"2026-03-03 11:01:14"}}