{"raw_statement":[{"iden":"problem statement","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."},{"iden":"constraints","content":"*   $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."},{"iden":"input","content":"The 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$"},{"iden":"sample input 1","content":"3 2\nWWB\nBBW\nWBW\n1 2 3 4\n0 3 4 5"},{"iden":"sample output 1","content":"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."},{"iden":"sample input 2","content":"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"},{"iden":"sample output 2","content":"621\n167\n44\n344\n500000000000000000"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}