F. Big Baozi, Small Baozi
time limit per test
4 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

DreamChaser is excited about a new video game, Big Baozi, Small Baozi. In this game, he plays as a Baozi trying to consume other Baozi to grow bigger.

The game's map is represented by an undirected connected graph with $$$n$$$ vertices and $$$m$$$ edges. Each vertex contains a Baozi with a weight $$$w_u$$$ ($$$1 \leq u \leq n$$$).

The game consists of $$$q$$$ rounds. At the start of each round:

  • The graph resets to its original state.
  • DreamChaser becomes the Baozi at vertex $$$v$$$ with an additional weight boost of $$$x$$$. Thus, his initial weight for that round is $$$w_v + x$$$. The values of $$$v$$$ and $$$x$$$ may vary across rounds.

After the round begins, DreamChaser can perform the following operation repeatedly:

  • If there is a neighboring Baozi with a weight no greater than his current weight, he consumes it.
  • When a Baozi is consumed, its weight is added to DreamChaser's weight.
  • The neighbors of the consumed Baozi become DreamChaser's neighbors.

This process continues until there are no consumable neighbors left. For each round of the game, please help DreamChaser determine his final weight at the end of the round.

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 1000$$$). The description of the test cases follows.

The first line of each test case contains three integers $$$n$$$, $$$m$$$ and $$$q$$$ ($$$1 \le n \le 2 \cdot 10^5$$$, $$$n - 1 \le m \le \min(2 \cdot 10^5, \frac{n(n-1)}{2})$$$, $$$1 \le q \le 2 \cdot 10^5$$$) — the number of vertices, edges, and rounds respectively.

The second line contains $$$n$$$ integers $$$w_1,,w_2,\ldots,w_n$$$ ($$$1 \le w_i \le 10^9$$$) — the weight of the Baozi on each vertex.

Each of the next $$$m$$$ lines contains two integers $$$u$$$ and $$$v$$$ ($$$1 \le u,v \le n$$$, $$$u \ne v$$$), representing an edge between vertices $$$u$$$ and $$$v$$$. It is guaranteed that there are no self loops or multiple edges in the graph.

Each of the next $$$q$$$ lines contains two integers $$$v$$$ and $$$x$$$ ($$$1 \le v \le n$$$, $$$0 \le x \le 10^9$$$) — the starting vertex and additional weight boost for each round.

It is guaranteed that the sum of $$$n$$$, $$$m$$$ and $$$q$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output

For each test case, output $$$q$$$ integers, where the $$$i$$$-th integer represents the final weight of DreamChaser for the $$$i$$$-th round.

Example
Input
1
5 4 4
1 2 2 5 11
1 2
2 3
5 4
3 4
1 0
4 0
4 1
2 10
Output
1
10
22
31