[ICPC2021 Nanjing R] Paimon Segment Tree

## 题目描述 派蒙刚刚学习了可持久化线段树，她想马上练习一下。因此，荧决定给她出一道简单的问题： 给定数列$a_1, a_2, \cdots, a_n$，并进行$m$次操作。操作包含3个参数$l_i$, $r_i$ ($1 \le l_i \le r_i \le n$) 和 $x_i$，代表对该序列第$l_i$到第$r_i$个元素加上$x_i$。 记$a_{i, t}$为$t$次操作后$a_i$的值。注意若$a_i$未被修改，则$a_{i,t}$的值与$a_{i,t-1}$相同。定义$a_{i, 0}$是$a_i$的初始值。 完成所有操作后，荧进行$q$次询问，询问包含4个整数$l_k$, $r_k$, $x_k$ and $y_k$，派蒙需要回答 $$\sum\limits_{i=l_k}^{r_k}\sum\limits_{j=x_k}^{y_k} a_{i, j}^2$$ 请将答案对$10^9 + 7$取模后输出。 ## 输入格式 每个测试点含一组测试数据。 第一行3个整数$n$,$m$,$q$ ($1 \le n, m, q \le 5 \times 10^4$) 分别表示数列的长度，操作的次数和询问的次数。 第2行$n$个整数 $a_1, a_2, \cdots, a_n$ ($|a_i| < 10^9 + 7$) ，表示原始数列。 接下来$m$行每行3个整数 $l_i$, $r_i$ $x_i$ ($1 \le l_i \le r_i \le n$, $|x_i| < 10^9 + 7$)，表示区间加操作。 接下来$q$行每行包含四个整数 $l_i$, $r_i$, $x_i$ $y_i$ ($1 \le l_i \le r_i \le n$, $0 \le x_i \le y_i \le m$)，表示询问。 ## 输出格式 对每个询问单起一行输出答案模$10^9 + 7$的结果。

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$.

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.

For each query output one line containing one integer indicating the answer modulo $10^9 + 7$.

3 1 1
8 1 6
2 3 2
2 2 0 0

1

4 3 3
2 3 2 2
1 1 6
1 3 3
1 3 6
2 2 2 3
1 4 1 3
4 4 2 3

180
825
8