You are planning on looting a temple. The temple has $N$ rooms numbered from $1$ to $N$, every pair of which is connected by a tunnel which takes $1$ second to traverse. Initially, $M$ of the tunnels are blocked and cannot be used. There is one treasure in each room, and you want to collect every treasure in the temple. You start in room $1$, the entrance of the temple, and can only traverse the temple by walking through tunnels. Since the treasures can be heavy, you can carry at most one at a time and must return to the entrance to store them after picking one up. When you pick up the $i^{\text{th}}$ treasure, it sets off some traps, increasing the amount of time it takes to walk through each tunnel by $a_i$ seconds. You would like to calculate the minimum amount of time it would take for you to collect every piece of treasure and return to the entrance.

Since the temple is quite old, the tunnels are not very sturdy and will slowly collapse over time. You know that in the future, $Q$ of the tunnels will collapse. You also know which tunnels will collapse and in what order. However, you don't know when exactly you will arrive at the temple. Therefore, you want to calculate for each $i$ from $1$ to $Q$ the minimum amount of time it would take for you to collect every treasure in the temple if you arrive right after the $i^{\text{th}}$ collapse event. You can assume that the events are spaced very far apart in time, and tunnels won't collapse while you are in the temple.

Constraints

$1\le N,M,Q\le 3\times {10}^5$

$0\le a_i\le {10}^6$ $(1\le i\le N)$

No tunnel will have its two endpoints being the same.

No tunnel will be specified more than once in the input.

The data will guarantee that it is always possible to reach every room from the entrance.

Subtask 1 [15%]

$1\le N,M,Q\le 300$

Subtask 2 [20%]

$Q=1$

Subtask 3 [25%]

$a_i=0$

Subtask 4 [40%]

No additional constraints.

Input Specification

The first line contains three integers, $N$, $M$, and $Q$, the number of rooms, the number of initially blocked tunnels, and the number of events, respectively.

The next line contains $N$ integers, $a_i$.

The next $M$ lines each contain two distinct integers, the endpoints of one of the blocked tunnels.

The next $Q$ lines each contain two distinct integers, the endpoints of the tunnel which collapses in this event.

Output Specification

Output $Q$ integers on separate lines, the $i^{\text{th}}$ of which is the amount of time it would take for you to collect every treasure if you arrived immediately after the $i^{\text{th}}$ event.

Sample Input

4 2 1
1 2 3 4
1 4
1 3
3 4

Sample Output

52

Explanation for Sample

After the first tunnel collapses, one optimal solution is to do the following steps:

1. Go through rooms $1\to 2\to 3$, which takes $2$ seconds.
2. Pick up the treasure in room $3$, which increases the amount of time it takes to go through a tunnel to $4$ seconds.
3. Go through rooms $3\to 2\to 1$, which takes $8$ seconds.
4. Put down the treasure you are carrying.
5. Go through rooms $1\to 2$, which takes $4$ seconds.
6. Pick up the treasure in room $2$, which increases the amount of time it takes to go through a tunnel to $6$ seconds.
7. Go through rooms $2\to 1$, which takes $6$ seconds.
8. Put down the treasure you are carrying.
9. Go through rooms $1\to 2\to 4$, which takes $12$ seconds.
10. Pick up the treasure in room $4$, which increases the amount of time it takes to go through a tunnel to $10$ seconds.
11. Go through rooms $4\to 2\to 1$, which takes $20$ seconds.
12. Put down the treasure you are carrying.
13. Pick up the treasure in room $1$.

This takes a total of $2+8+4+6+12+20=52$ seconds.