说明

有 $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$。这些变更是永久性的。在每次变更后，输出在新条件下政策可能获得的最大声誉。

输入格式

输入格式如下：

$$\begin{aligned} & N \ M \ Q \\ & L_0 \ L_1 \ \ldots \ L_{N-1} \\ & X_1 \ Y_1 \\ & X_2 \ Y_2 \\ & \vdots \\ & X_M \ Y_M \\ & T_1 \ Z_1 \\ & T_2 \ Z_2 \\ & \vdots \\ & T_Q \ Z_Q \end{aligned}$$

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

输出格式

输出 $Q$ 行。在第 $k$ 行（$1 \leq k \leq Q$），输出第 $k$ 个询问的答案。可以证明答案是整数。

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

8
7
8
15

提示

翻译由 DeepSeek V3.2 完成