Paimon Segment Tree

Paimon just learned the persistent segment tree and wants to practice right away. So Lumine gives her an easy problem to start with.

You are given a sequence $a_1, a_2, \cdots, a_n$ of length $n$. Lumine applies $m$ modifications to it. The $i$-th modification is given by three integers $l_i$, $r_i$ ($1 \le l_i \le r_i \le n$) and $x_i$, and changes $a_k$ to $a_k + x_i$ for every $k$ with $l_i \le k \le r_i$.

Let $a_{i,t}$ be the value of $a_i$ just after the $t$-th modification, so every past version of $a_i$ is tracked this way. If the $t$-th modification does not touch $a_i$, then $a_{i,t}$ equals $a_{i,t-1}$. For completeness, $a_{i,0}$ is the initial value of $a_i$.

After all modifications, Lumine gives Paimon $q$ queries. The $k$-th query is given by four integers $l_k$, $r_k$, $x_k$, $y_k$, and asks for

$\sum_{i=l_k}^{r_k}\sum_{j=x_k}^{y_k} a_{i,j}^2$

Compute the answer to every query. The answers can be very large, so print each one modulo $10^9 + 7$.

The first line has three integers $n$, $m$, $q$ ($1 \le n, m, q \le 5 \times 10^4$): the length of the sequence, the number of modifications, and the number of queries.

The second line has $n$ integers $a_1, a_2, \cdots, a_n$ ($|a_i| < 10^9 + 7$), the initial sequence.

Each of the next $m$ lines has $l_i$, $r_i$, $x_i$ ($1 \le l_i \le r_i \le n$, $|x_i| < 10^9 + 7$), describing one modification.

Each of the next $q$ lines has $l_k$, $r_k$, $x_k$, $y_k$ ($1 \le l_k \le r_k \le n$, $0 \le x_k \le y_k \le m$), describing one query.

There is only one test case per input file.

For each query, print the answer modulo $10^9 + 7$ on its own line.