Problem Description

After being discharged from the hospital following a needle injection, mzry1992 bought a new motorcycle and started a gold transportation business in nearby cities. In the area where mzry1992 lives, cities are connected by bidirectional highways, each with a weight limit. This limit means that without considering the weight of the driver and the motorcycle, if the cargo exceeds a certain value, the highway cannot be used.

This year, mzry1992 received a total of $n$ orders from $n$ different cities, each order specifying a maximum amount of gold to be sold or bought. Since the orders did not arrive simultaneously, to maintain his business reputation, mzry1992 had to conduct transactions with customers in the order the orders were received. The specific steps for trading with the $i$-th customer are:

1. Travel to the city of the $i$-th customer. It is permissible to pass through other cities en route.
2. Conduct a transaction with the $i$-th customer, aiming to maximize the transaction amount within certain limits:
   (a) He hopes to have no remaining gold after completing the transaction with the last customer.
   (b) Since gold is a precious item, it should not be possible to buy too much gold, leading to the necessity of discarding gold during later transportation.

Initially, mzry1992 is located in the city of the first order's customer. There is good news: someone has provided mzry1992 with a free trial of the train system in nearby cities. Specifically, if mzry1992 wishes to travel from city $A$ to city $B$, and both cities have train stations, he can take the train from city $A$ to city $B$ with his gold and motorcycle, assuming there is no weight limit on the train.

Given the city transportation system and order details, help mzry1992 calculate the amount of gold each customer buying gold from him should purchase.

Input Format

The first line of input contains three integers $n, m, q$, representing the number of cities, the number of highways connecting cities, and the number of cities with train stations, respectively.

The next line contains $n$ numbers, each unique and ranging from $1$ to $n$, representing the order sequence.

The third line contains $n$ numbers, where the $i$-th number represents the order limit $b_i$ of city $i$. A positive $b_i$ indicates a buy order (from mzry1992's perspective) with a limit of $b_i$, and a negative $b_i$ indicates a sell order with a limit of $-b_i$.

The following $m$ lines each contain three numbers, $u, v, w$, indicating that there is a highway between city $u$ and city $v$ with a weight limit of $w$. All highways are bidirectional, and city numbers range from $1$ to $n$.

The last line contains $q$ numbers, representing the city numbers with train stations.

Output Format

For each sell order in the order sequence, output a line containing a single integer $x$, representing the amount of gold sold.

Sample Input and Output

Input Sample #1

3 3 2
2 3 1
-6 5 -3
1 3 5
2 3 2
2 1 6
1 3

Output Sample #1

3
2

Input Sample #2

4 4 0
1 2 3 4
5 4 -6 -1
1 2 4
2 3 100
3 4 1
4 1 4

Output Sample #2

6
1

Notes/Hints

Sample Explanation

First Sample: One valid scheme is to initially buy 5 units of gold in city 2, travel to city 1 via the third highway, then take the train to city 3, sell 3 units of gold in city 3, take the train back to city 1, and sell 2 units of gold in city 1.

Second Sample: One valid scheme is to initially buy 4 units of gold in city 1, travel via the first highway, buy 3 units of gold in city 2, travel via the second highway, sell 6 units of gold in city 3, travel via the third highway, and sell 1 unit of gold in city 4.

Data Range and Constraints

• For $20\%$ of the data, $n \le 100$, $m \le 200$.
• For $50\%$ of the data, $n \le 3000$, $m \le 6000$.
• For $100\%$ of the data, $1 \le n \le 10^5$, $n - 1 \le m \le 2 \times 10^5$, $0 \le q \le n$, $0 < |b_i| < 10^9$, $0 < w < 10^9$, and it is guaranteed that any two cities are connected by highways.

见题面 Input 部分

见题面 Output 部分