{"raw_statement":[{"iden":"problem statement","content":"We have a grid with $N$ rows and $M$ columns. The square $(i,j)$ at the $i$\\-th row from the top and $j$\\-th column from the left has an integer $(i-1) \\times M + j$ written on it.  \nLet us perform the following operation on this grid.\n\n*   For every square $(i,j)$ such that $i+j$ is odd, replace the integer on that square with $0$.\n\nAnswer $Q$ questions on the grid after the operation.  \nThe $i$\\-th question is as follows:\n\n*   Find the sum of the integers written on all squares $(p,q)$ that satisfy all of the following conditions, modulo $998244353$.\n    *   $A_i \\le p \\le B_i$.\n    *   $C_i \\le q \\le D_i$."},{"iden":"constraints","content":"*   All values in the input are integers.\n*   $1 \\le N,M \\le 10^9$\n*   $1 \\le Q \\le 2 \\times 10^5$\n*   $1 \\le A_i \\le B_i \\le N$\n*   $1 \\le C_i \\le D_i \\le M$"},{"iden":"input","content":"The input is given from Standard Input in the following format:\n\n$N$ $M$\n$Q$\n$A_1$ $B_1$ $C_1$ $D_1$\n$A_2$ $B_2$ $C_2$ $D_2$\n$\\vdots$\n$A_Q$ $B_Q$ $C_Q$ $D_Q$"},{"iden":"sample input 1","content":"5 4\n6\n1 3 2 4\n1 5 1 1\n5 5 1 4\n4 4 2 2\n5 5 4 4\n1 5 1 4"},{"iden":"sample output 1","content":"28\n27\n36\n14\n0\n104\n\nThe grid in this input is shown below.  \n![image](https://img.atcoder.jp/abc269/81d92debe7aa949266f3a00cff13b513.png)\nThis input contains six questions.\n\n*   The answer to the first question is $0+3+0+6+0+8+0+11+0=28$.\n*   The answer to the second question is $1+0+9+0+17=27$.\n*   The answer to the third question is $17+0+19+0=36$.\n*   The answer to the fourth question is $14$.\n*   The answer to the fifth question is $0$.\n*   The answer to the sixth question is $104$."},{"iden":"sample input 2","content":"1000000000 1000000000\n3\n1000000000 1000000000 1000000000 1000000000\n165997482 306594988 719483261 992306147\n1 1000000000 1 1000000000"},{"iden":"sample output 2","content":"716070898\n240994972\n536839100\n\nFor the first question, note that although the integer written on the square $(10^9,10^9)$ is $10^{18}$, you are to find it modulo $998244353$."},{"iden":"sample input 3","content":"999999999 999999999\n3\n999999999 999999999 999999999 999999999\n216499784 840031647 84657913 415448790\n1 999999999 1 999999999"},{"iden":"sample output 3","content":"712559605\n648737448\n540261130"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}