题目描述

Paimon 刚刚学会了可持久化线段树，决定立刻练习一下。于是，Lumine 给了她一个简单的练习题：

给定一个长度为 $n$ 的序列 $a_1, a_2, \cdots, a_n$， Lumine 会对这个序列进行 $m$ 次修改。在第 $i$ 次修改中，给出三个整数 $l_i, r_i, x_i \ (1 \le l_i \le r_i \le n)$，Lumine 会将所有满足 $l_i \le k \le r_i$ 的元素 $a_k$ 修改为 $(a_k + x_i)$。

定义 $a_{i,t}$ 为第 $t$ 次操作之后的 $a_i$ 的值。这样我们就能记录下每个 $a_i$ 在历史上的所有版本。 注意，如果 $a_i$ 在第 $t$ 次修改中没有被修改，则有 $a_{i,t} = a_{i,t-1}$。为方便起见，我们也定义 $a_{i,0}$ 为 $a_i$ 的初始值。

在所有修改完成后，荧会给派蒙 $q$ 个询问，询问关于这些历史值的平方和。 第 $k$ 个询问由四个整数 $l_k, r_k, x_k, y_k$ 表示，要求派蒙计算：

请帮助 Paimon 计算所有询问的结果。由于答案可能非常大，请将结果对 $10^9 + 7$ 取模后输出。

输入格式

每个测试文件中只有一组数据。

第一行包含三个整数 $n, m, q$ $(1 \le n, m, q \le 5 \times 10^4)$ 分别表示序列的长度、修改次数和询问次数。

第二行包含 $n$ 个整数 $a_1, a_2, \cdots, a_n$ $(|a_i| < 10^9 + 7)$ 表示序列的初始值。

接下来 $m$ 行中，第 $i$ 行包含三个整数 $l_i, r_i, x_i$ $(1 \le l_i \le r_i \le n, |x_i| < 10^9 + 7)$ 表示第 $i$ 次修改。

接下来 $q$ 行中，第 $i$ 行包含四个整数 $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)$ 表示第 $i$ 次询问。

输出格式

对于每个询问，输出一行，一个整数，表示答案对 $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