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\)