Paimon 刚刚学习了可持久化线段树，并决定立即进行练习。因此，Lumine 给她出了一个简单的入门题：

给定一个长度为 $n$ 的序列 $a_1, a_2, \dots, a_n$，Lumine 将对该序列进行 $m$ 次修改。在第 $i$ 次修改中，由三个整数 $l_i, r_i$ ($1 \le l_i \le r_i \le n$) 和 $x_i$ 表示，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$ 的初始值。

在所有修改完成后，Lumine 会给 Paimon $q$ 个关于历史值平方和的查询。第 $k$ 个查询由四个整数 $l_k, r_k, x_k$ 和 $y_k$ 表示，需要 Paimon 计算：

$$\sum_{i=l_k}^{r_k} \sum_{j=x_k}^{y_k} a_{i,j}^2$$

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

输入格式

每个测试文件中仅包含一组测试数据。

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

第二行包含 $n$ 个整数 $a_1, a_2, \dots, 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$ 取模的结果。

样例

样例输入 1

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

样例输出 1

1

样例输入 2

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

样例输出 2

180
825
8