{"problem":{"name":"Tile Pattern","description":{"content":"There is a grid with $10^9$ by $10^9$ squares. Let $(i, j)$ denote the square at the $(i + 1)$\\-th row from the top and the $(j + 1)$\\-th column from the left $(0 \\leq i, j \\lt 10^9)$. (Note the unusu","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc331_d"},"statements":[{"statement_type":"Markdown","content":"There is a grid with $10^9$ by $10^9$ squares. Let $(i, j)$ denote the square at the $(i + 1)$\\-th row from the top and the $(j + 1)$\\-th column from the left $(0 \\leq i, j \\lt 10^9)$. (Note the unusual index assignment.)  \nEach square is black or white. The color of the square $(i, j)$ is represented by a character $P[i \\bmod N][j \\bmod N]$, where `B` means black, and `W` means white. Here, $a \\bmod b$ denotes the remainder when $a$ is divided by $b$.\nAnswer $Q$ queries.  \nEach query gives you four integers $A, B, C, D$ and asks you to find the number of black squares contained in the rectangular area with $(A, B)$ as the top-left corner and $(C, D)$ as the bottom-right corner.\n\n## Constraints\n\n*   $1 \\leq N \\leq 1000$\n*   $P[i][j]$ is `W` or `B`.\n*   $1 \\leq Q \\leq 2 \\times 10^5$\n*   $0 \\leq A \\leq C \\lt 10^9$\n*   $0 \\leq B \\leq D \\lt 10^9$\n*   $N, Q, A, B, C, D$ are all integers.\n\n## Input\n\nThe input is given from Standard Input in the following format. Here, $\\text{query}_i$ is the $i$\\-th query to be processed.\n\n$N$ $Q$\n$P[0][0]P[0][1]\\dots P[0][N-1]$\n$P[1][0]P[1][1]\\dots P[1][N-1]$\n$\\vdots$\n$P[N-1][0]P[N-1][1]\\dots P[N-1][N-1]$\n$\\text{query}_1$\n$\\text{query}_2$\n$\\vdots$\n$\\text{query}_Q$\n\nEach query is given in the following format:\n\n$A$ $B$ $C$ $D$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc331_d","tags":[],"sample_group":[["3 2\nWWB\nBBW\nWBW\n1 2 3 4\n0 3 4 5","4\n7\n\nThe figure below illustrates the upper left part of the grid.\n![image](https://img.atcoder.jp/abc331/2c3ff3c4018817a0839f1fbe0e7c431d.jpg)\nFor the first query, the rectangular area with $(1, 2)$ as the top-left corner and $(3, 4)$ as the bottom-right corner, surrounded by the red frame in the figure, contains four black squares.  \nFor the second query, the rectangular area with $(0, 3)$ as the top-left corner and $(4, 5)$ as the bottom-right corner, surrounded by the blue frame in the figure, contains seven black squares."],["10 5\nBBBWWWBBBW\nWWWWWBBBWB\nBBBWBBWBBB\nBBBWWBWWWW\nWWWWBWBWBW\nWBBWBWBBBB\nWWBBBWWBWB\nWBWBWWBBBB\nWBWBWBBWWW\nWWWBWWBWWB\n5 21 21 93\n35 35 70 43\n55 72 61 84\n36 33 46 95\n0 0 999999999 999999999","621\n167\n44\n344\n500000000000000000"]],"created_at":"2026-03-03 11:01:14"}}