Description

There are $N$ cities numbered from $0$ to $N - 1$. A railway goes around all $N$ cities, and city $i$ and city $(i + 1) \bmod N$ can be traveled between in $L_i$ time units.

You will implement the following policy:

• You may construct any number of railways that allow travel between any two cities in any non-negative time.
• You then select one city among the $N$ cities to be the capital. The minimum travel time from the capital to city $i$ using the railways is defined as that city's undevelopment index $d_i$.

The reputation of this policy will be determined by word of mouth from the $M$ residents who will move this year. Resident $j$ will move from city $X_j$ to city $Y_j$ after the policy is implemented. The reputation will be the sum of $d_{X_j} - d_{Y_j}$.

Your goal is to maximize the reputation of the policy. However, renovation work on the existing railway is also in progress, and you must revise the policy accordingly.

The travel times of existing railways will change $Q$ times. At the $k$-th change, the travel time between city $T_k$ and city $(T_k + 1) \bmod N$ changes to $Z_k$. These changes are persistent. After each change, output the maximum possible reputation of the policy under the new conditions.

Input Format

The input is given in the following format:

$$\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$)
• All input values are integers.

Output Format

Output $Q$ lines. On the $k$-th line ($1 \leq k \leq Q$), output the answer for the query $k$. It can be proven that the answer is an integer.

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