Persistent Segment Tree Practice: Sum of Squares Queries

Paimon just learned the persistent segment tree and decides to practice immediately. Lumine gives her an easy problem to start:

Given a sequence \(a_1, a_2, \dots, 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\) (with \(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. We define \(a_{i,0}\) as the initial value of \(a_i\). After all modifications have been applied, Paimon needs to answer \(q\) queries. The \(k\)-th query is given by four integers \(l_k, r_k, x_k, y_k\) and asks to compute:

\[ \sum_{i=l_k}^{r_k} \sum_{j=x_k}^{y_k} a_{i,j}^2 \pmod{10^9+7} \]

Note: It is guaranteed that answers should be output modulo \(10^9+7\).

Input and Output formats are described below.

inputFormat

Format:

n m q
a1 a2 ... an
(l1 r1 x1)
...
(lm rm xm)
(l1 r1 x1 y1)
...
(lq rq xq yq)

Note: The sequence indices are 1-indexed. The historical version index \(j\) ranges from 0 (initial sequence) to \(m\) (after all modifications).

outputFormat

Format:

result1
result2
...
resultq

Each line contains the answer to the respective query computed modulo \(10^9+7\).

sample

3 2 2
1 2 3
1 2 1
2 3 2
1 3 0 0
1 2 1 2

14
42

</p>