A country consists of $n$ cities connected by $(n - 1)$ multidimensional roads, where each road has length $l_i$ meters. A group of friends want to purchase a jewelry piece.

There are $m$ jewelry pieces in the country and each of them is located in some city $c_i$ and has a value $v_i$. Each friend cannot walk for more than $w_i$ meters.

Your task is to determine the highest value of the jewelry piece that you can buy if a friend started walking from city $1$ and returns to the same city after the purchase.

Input format

• First line: Three integers $n$, $m$, and $k$ denoting the number of cities, number of jewelry pieces, and number of friends
• Second line: $k$ integers $w_i$ denoting the number of meters the $i^{th}$ friend can walk
• Each of the next $n - 1$ lines: Three integers $a_i$, $b_i$, and $l_i$ denoting the road from city $a_i$ to city $b_i$ and length $l_i$ meters 
• Each of the next $m$ lines: Two integers $c_j$ and $v_j$denoting the city that consists of the jewelry pieces and the value of each piece

Output format

Print $k$ integers, where the $i^{th}$ value represents the highest value of jewelry piece that they bought. The $i^{th}$ friend can buy the jewelry piece if he or she started walking from city $1$ and returned to the same city after the purchase.

Constraints

$1 \leq n \leq 1000\\ 1 \leq m \leq 10^6\\ 1 \leq k \leq 10^6\\ 1 \leq w_i \leq 1000\\ 1 \leq l_i \leq 1000\\ 1 \leq v_j \leq 10^9$