有 $N$ 个城市，编号为 $0$ 到 $N - 1$。有一条环形铁路连接了所有 $N$ 个城市，在城市 $i$ 与城市 $(i + 1) \bmod N$ 之间旅行需要 $L_i$ 个单位的时间。

你将实施以下政策：

• 你可以建设任意数量的铁路，允许在任意两个城市之间以任意非负时间进行旅行。
• 然后，你在这 $N$ 个城市中选择一个城市作为首都。使用铁路从首都到城市 $i$ 的最短旅行时间被定义为该城市的欠发达指数 $d_i$。

该政策的声誉将由今年将要搬迁的 $M$ 位居民的口碑决定。在政策实施后，居民 $j$ 将从城市 $X_j$ 移动到城市 $Y_j$。政策的声誉将是所有居民的 $d_{X_j} - d_{Y_j}$ 之和。

你的目标是最大化该政策的声誉。然而，现有铁路的改造工作也在进行中，你必须相应地调整政策。

现有铁路的旅行时间将发生 $Q$ 次变化。在第 $k$ 次变化中，城市 $T_k$ 与城市 $(T_k + 1) \bmod N$ 之间的旅行时间将变为 $Z_k$。这些变化是持久的。在每次变化后，输出在新条件下该政策可能达到的最大声誉。

输入格式

输入格式如下：

N M Q
L_0 L_1 ... L_{N-1}
X_1 Y_1
X_2 Y_2
...
X_M Y_M
T_1 Z_1
T_2 Z_2
...
T_Q Z_Q

数据范围

• $3 \le N \le 200\,000$
• $1 \le M \le 200\,000$
• $1 \le Q \le 200\,000$
• $0 \le L_i \le 10^6$ ($1 \le i \le N$)
• $0 \le X_j, Y_j \le N - 1$ ($1 \le j \le M$)
• $X_j \neq Y_j$ ($1 \le j \le M$)
• $0 \le T_k \le N - 1$ ($1 \le k \le Q$)
• $0 \le Z_k \le 10^6$ ($1 \le k \le Q$)
• 所有输入值均为整数。

输出格式

输出 $Q$ 行。在第 $k$ 行（$1 \le k \le Q$）输出第 $k$ 次查询的答案。可以证明，答案一定是一个整数。

样例

输入样例 1

5 3 4
1 5 2 1 3
0 2
1 3
4 2
4 0
1 3
4 2
3 9

输出样例 1

8
7
8
15