随着光芒洒向海岛，每个房屋内的权力流动开始发生变化。随着时间的推移，它来回移动，其痕迹被悄悄记录下来。

人们试图追溯权力流经的每一个瞬间，希望能找到其最强联盟的契机。

现在，跟随他们曾经共享的流动——并恢复那些已经丢失的记录。

在岛上的一个村庄里，有 $N$ 间房屋排成一排，从左到右依次编号为 $1$ 到 $N$。

在第 $0$ 天，房屋 $i$ 的初始权力值为 $a_i$。

在接下来的 $M$ 天里，发生了一种神秘的现象：权力在相邻的房屋之间转移。具体来说，在第 $i$ 天，房屋 $x_i$ 的权力值增加了 $v_i$，而房屋 $x_i + 1$ 的权力值减少了 $v_i$。（$v_i$ 可能为负数。）

村民们在一个网格中记录了权力随时间推移的变化过程。例如，如果 $N = 4$，$M = 5$，$a = [3, -2, 2, -2]$，$x = [3, 1, 2, 1, 2]$ 且 $v = [-4, -2, 3, 2, -4]$，则权力随时间变化的网格（其中每行代表一天，每列代表一间房屋）如下所示：

随着权力的不断转移，一些村民试图建立一个联盟（coalition），以加强房屋之间的团结并平衡权力的分配。建立联盟的过程如下：

• 选择一天 $t$ 和一个主导房屋编号 $x$。（$0 \le t \le M$，$1 \le x \le N$）
• 选择一个包含 $x$ 的连续房屋区间 $[l, r]$。（$1 \le l \le x \le r \le N$）
• 联盟的权力定义为在第 $t$ 天，区间 $[l, r]$ 内所有房屋的权力值之和。
  • 此时，定义 $P_{tx}$ 为在给定的 $t$ 和 $x$ 下，所能达到的最大联盟权力。

为了有效地规划他们的联盟，人们希望比较不同时间段和不同房屋配置下的潜在权力。在此过程中，提出了 $Q$ 个问题。第 $i$ 个问题如下：

• 对于所有满足 $s_i \le t \le e_i$ 且 $l_i \le x \le r_i$ 的双元组 $(t, x)$，他们的 $P_{tx}$ 的总和是多少？

请高效地回答这些问题，帮助确定每个可能联盟方案的强度。

输入格式

第一行包含三个空格分隔的整数 $N$、$M$ 和 $Q$。

第二行包含 $N$ 个空格分隔的整数 $a_1, a_2, \dots, a_N$，代表房屋的初始权力值。

接下来的 $M$ 行，每行包含两个空格分隔的整数 $x_i$ 和 $v_i$，代表权力转移的信息。这意味着在第 $i$ 天，房屋 $x_i$ 的权力值增加 $v_i$，而房屋 $x_i + 1$ 的权力值减少 $v_i$。

接下来的 $Q$ 行，每行包含四个空格分隔的整数 $s_i, e_i, l_i, r_i$，代表每个问题。

数据范围

• $2 \le N \le 10^5$
• $1 \le M \le 10^5$
• $1 \le Q \le 10^5$
• $-10^9 \le a_i \le 10^9$ ($1 \le i \le N$)
• $1 \le x_i < N$ ($1 \le i \le M$)
• $-10^9 \le v_i \le 10^9$ ($1 \le i \le M$)
• $0 \le s_i \le e_i \le M$ ($1 \le i \le Q$)
• $1 \le l_i \le r_i \le N$ ($1 \le i \le Q$)

输出格式

对于每个问题，输出其答案模 $10^9 + 7$ 的结果，每行一个。

子任务

• 子任务 1（8 分）：$N \le 2000$，$M \le 2000$，$Q \le 1000$，$s_i = e_i$ 且 $l_i = r_i$（$1 \le i \le Q$）
• 子任务 2（16 分）：$N \le 2000$，$M \le 2000$，$s_i = e_i$ 且 $l_i = r_i$（$1 \le i \le Q$）
• 子任务 3（10 分）：$s_i = e_i$ 且 $l_i = r_i$（$1 \le i \le Q$）
• 子任务 4（19 分）：$s_i = e_i$（$1 \le i \le Q$）
• 子任务 5（17 分）：$l_i = r_i$（$1 \le i \le Q$）
• 子任务 6（30 分）：无附加限制。

样例

输入样例 1

4 5 4
3 -2 2 -2
3 -4
1 -2
2 3
1 2
2 -4
1 3 1 2
3 4 3 4
0 2 2 2
0 5 1 4

输出样例 1

14
6
5
51

输入样例 2

3 2 9
3 -2 1
1 -3
2 -2
0 0 1 1
0 0 2 2
0 0 3 3
1 1 1 1
1 1 2 2
1 1 3 3
2 2 1 1
2 2 2 2
2 2 3 3

输出样例 2

3
2
2
2
2
2
2
2
3