{"raw_statement":[{"iden":"statement","content":"Paimon just learns the persistent segment tree and decides to practice immediately. Therefore, Lumine gives her an easy problem to start:\n\nGiven a sequence $a_1, a_2, \\cdots, a_n$ of length $n$, Lumine will apply $m$ modifications to the sequence. In the $i$-th modification, indicated by three integers $l_i$, $r_i$ ($1 \\le l_i \\le r_i \\le n$) and $x_i$, Lumine will change $a_k$ to $(a_k + x_i)$ for all $l_i \\le k \\le r_i$.\n\nLet $a_{i, t}$ be the value of $a_i$ just after the $t$-th operation. This way we can keep track of all historial versions of $a_i$. Note that $a_{i,t}$ might be the same as $a_{i,t-1}$ if it hasn't been modified in the $t$-th modification. For completeness we also define $a_{i, 0}$ as the initial value of $a_i$.\n\nAfter all modifications have been applied, Lumine will give Paimon $q$ queries about the sum of squares among the historical values. The $k$-th query is indicated by four integers $l_k$, $r_k$, $x_k$ and $y_k$ and requires Paimon to calculate\n\n$$\\sum\\limits_{i=l_k}^{r_k}\\sum\\limits_{j=x_k}^{y_k} a_{i, j}^2$$\n\nPlease help Paimon compute the result for all queries. As the answer might be very large, please output the answer modulo $10^9 + 7$."},{"iden":"input","content":"There is only one test case in each test file.\n\nThe first line of the input contains three integers $n$, $m$ and $q$ ($1 \\le n, m, q \\le 5 \\times 10^4$) indicating the length of the sequence, the number of modifications and the number of queries.\n\nThe second line contains $n$ integers $a_1, a_2, \\cdots, a_n$ ($|a_i| < 10^9 + 7$) indicating the initial sequence.\n\nFor the following $m$ lines, the $i$-th line contains three integers $l_i$, $r_i$ and $x_i$ ($1 \\le l_i \\le r_i \\le n$, $|x_i| < 10^9 + 7$) indicating the $i$-th modification.\n\nFor the following $q$ lines, the $i$-th line contains four integers $l_i$, $r_i$, $x_i$ and $y_i$ ($1 \\le l_i \\le r_i \\le n$, $0 \\le x_i \\le y_i \\le m$) indicating the $i$-th query."},{"iden":"output","content":"For each query output one line containing one integer indicating the answer modulo $10^9 + 7$."}],"translated_statement":null,"sample_group":[["3 1 1\n8 1 6\n2 3 2\n2 2 0 0\n","1\n"],["4 3 3\n2 3 2 2\n1 1 6\n1 3 3\n1 3 6\n2 2 2 3\n1 4 1 3\n4 4 2 3\n","180\n825\n8\n"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}