A. Antivirus
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output
In the introduction to network flow, the teacher had barely begun explaining when their pet chicken figured out how to solve the problem. The teacher exclaimed: Our avian flu is amazing!
—Roasted-chicken

Hyrule is entering the flu season.

Hyrule consists of $$$n$$$ cities, which are connected by $$$m$$$ directed roads. The capital (city numbered $$$1$$$) can be reached from all cities through these roads.

The flu season will last for $$$q$$$ days. On the $$$i$$$-th day at noon, the flu virus will start spreading from city $$$a_i$$$. The virus will spread along the roads to other cities. The virus spreads very quickly, so it can be assumed that all cities reachable from $$$a_i$$$ will be infected immediately. As the capital city of Hyrule, city $$$1$$$ is crucial for the whole country. If the virus that starts spreading on the $$$i$$$-th day reaches the capital, there will be an economic loss cost of $$$b_i$$$.

To prevent the virus from spreading, Auru can deploy a virus filter in a city each night (including the night before the first day). Deploying a virus filter in city $$$i$$$ has a deployment cost of $$$c_i$$$. The virus cannot spread through the city equipped with a virus filter, and that city will also remain uninfected. If the virus were to start spreading from a city equipped with a virus filter, the virus would simply disappear without infecting any cities. The deployed virus filter remains effective until Auru deploys a new filter in another city. (In other words, there can be at most one virus filter at a time.)

Auru wants to know: for each $$$i = 1, 2, \dots, q$$$, considering only the viruses in the first $$$i$$$ days, what is the minimum value of "economic loss cost + deployment cost".

Input

Each test file contains multiple test cases. The first line contains the number of test cases $$$T$$$ ($$$1 \leq T \leq 10^4$$$). The description of the test cases follows.

The first line contains three integers $$$n$$$, $$$m$$$, and $$$q$$$ ($$$2 \leq n \leq 10^5$$$, $$$n-1 \leq m \leq 2 \times 10^5$$$, $$$1 \leq q \leq 10^5$$$), representing the number of cities, the number of roads, and the duration of the flu season in days, respectively.

In the next $$$m$$$ lines, each contains two integers $$$u_i$$$ and $$$v_i$$$ ($$$1 \leq u_i, v_i \leq n$$$), representing a directed road from city $$$u_i$$$ to city $$$v_i$$$. It is guaranteed that there are no self-loops, but there may be multiple edges between cities. The capital can be reached from all cities.

The next line contains $$$n$$$ integers $$$c_1, c_2, \dots, c_n$$$ ($$$1 \leq c_i \leq 10^9$$$), representing the deployment cost of the virus filter in each city.

In the following $$$q$$$ lines, the $$$i$$$-th one contains two integers $$$a_i$$$ and $$$b_i$$$ ($$$2 \leq a_i \leq n$$$, $$$1 \leq b_i \leq 10^9$$$), indicating the city where the virus starts to spread on the $$$i$$$-th day and the economic loss cost if the virus reaches the capital.

For each test file, it is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^5$$$, the sum of $$$m$$$ over all test cases does not exceed $$$2 \times 10^5$$$, and the sum of $$$q$$$ over all test cases does not exceed $$$10^5$$$.

Output

For each test case, output a line containing $$$n$$$ integers, where the $$$i$$$-th integer represents the minimum value of the "economic loss cost + deployment cost" when only considering the viruses in the first $$$i$$$ days.

Example
Input
3
7 6 4
2 1
3 1
4 2
5 2
6 3
7 3
4 3 5 2 2 1 1
4 2
5 2
6 2
7 2
5 6 4
1 3
3 2
2 1
4 2
5 4
2 5
10000 10000 2 100 5
5 1000
4 1000
3 1000
4 1000
4 4 1
2 1
3 1
4 2
4 3
100 1 1 100
4 10
Output
2 3 4 4
5 100 102 202
10
Note

In the first test case:

  • The minimum cost after day $$$1$$$ is $$$2$$$: on night $$$0$$$, deploy a virus filter in city $$$4$$$ with a deployment cost of $$$2$$$.
  • The minimum cost after day $$$2$$$ is $$$3$$$: on night $$$0$$$, deploy a virus filter in city $$$2$$$ with a deployment cost of $$$3$$$.
  • The minimum cost after day $$$3$$$ is $$$4$$$: on night $$$0$$$, deploy a virus filter in city $$$2$$$ with a deployment cost of $$$3$$$; on night $$$2$$$, deploy a virus filter in city $$$6$$$ with a deployment cost of $$$1$$$.
  • The minimum cost after day $$$4$$$ is $$$4$$$: on night $$$0$$$, deploy a virus filter in city $$$1$$$ with a deployment cost of $$$4$$$.

Example $$$1$$$ Illustration

In the second test case:

  • The minimum cost after day $$$1$$$ is $$$5$$$: on night $$$0$$$, deploy a virus filter in city $$$5$$$ with a deployment cost of $$$5$$$.
  • The minimum cost after day $$$2$$$ is $$$100$$$: on night $$$0$$$, deploy a virus filter in city $$$4$$$ with a deployment cost of $$$100$$$.
  • The minimum cost after day $$$3$$$ is $$$102$$$: on night $$$0$$$, deploy a virus filter in city $$$4$$$ with a deployment cost of $$$100$$$; on night $$$2$$$, deploy a virus filter in city $$$3$$$ with a deployment cost of $$$2$$$.
  • The minimum cost after day $$$4$$$ is $$$202$$$: on night $$$0$$$, deploy a virus filter in city $$$4$$$ with a deployment cost of $$$100$$$; on night $$$2$$$, deploy a virus filter in city $$$3$$$ with a deployment cost of $$$2$$$; on night $$$3$$$, deploy a virus filter in city $$$4$$$ again with a deployment cost of $$$100$$$.

Example $$$2$$$ Illustration

In the third test case, since only one virus filter can exist at a time, it is not possible to stop the virus from spreading by deploying virus filters in both cities $$$2$$$ and $$$3$$$. The deployment costs for cities $$$1$$$ and $$$4$$$ are higher than the economic loss cost caused by the virus, so no virus filter is deployed, and the minimum cost is $$$10$$$ (economic loss cost).

Example $$$3$$$ Illustration