P9844 [ICPC 2021 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$ 和 $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$ 的结果。

数据范围见输入格式。