Paimon just learns the persistent segment tree and decides to practice immediately. Therefore, Lumine gives her an easy problem to start:
Given 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$.
Let $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$.
After 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
$$\sum\limits_{i=l_k}^{r_k}\sum\limits_{j=x_k}^{y_k} a_{i, j}^2$$
Please help Paimon compute the result for all queries. As the answer might be very large, please output the answer modulo $10^9 + 7$.
## Input
There is only one test case in each test file.
The 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.
The second line contains $n$ integers $a_1, a_2, \cdots, a_n$ ($|a_i| < 10^9 + 7$) indicating the initial sequence.
For 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.
For 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.
## Output
For each query output one line containing one integer indicating the answer modulo $10^9 + 7$.
[samples]