题目描述

派蒙刚刚学习了可持久化线段树，她想马上练习一下。因此，荧决定给她出一道简单的问题：

给定数列 $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$ 的结果。

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

说明/提示

数据范围见输入格式。