At the dawn of time, there existed $n$ towns in southern Finland numbered $1,2,\dots,n$. The $i$-th town initially had $a_i$ citizens. Over time, the towns started to spread and merge, eventually forming cities.

You are presented with the history of the towns. The history has $m$ entries numbered $1,2,\dots,m$, the $i$-th of which records that towns $u_i$ and $v_i$ merged during year $i$ and the population of the city they belong to increased by $w_i$.

You are also given $q$ queries numbered $1,2,\dots,q$ of the form: $x_j\ y_j$ - what's the population count of the city town $x_j$ belongs to at the end of year $y_j$?

Input

The first line contains three integers $n$,$m$, and $q$. The second line contains $n$ integers $a_1,\,a_2,\ldots,\,a_n$. The $𝑖$-th of the next $m$ lines contains three integers $u_i$, $v_𝑖$, and $w_i$. The $𝑖$-th of the next $q$ lines contains two integers $x_i$, and $y_𝑖$.

Output

Print the answers to the queries on a single line.

Constraints

• $2 \leq n \leq 10^5$
• $1 \leq m, q \leq 2 \times 10^5$
• $1 \leq a_i \leq 100$
• $1 \leq u_i < v_i \leq n$
• $1 \leq w_i \leq 1000$
• $(u_i, v_i) \neq (u_j, v_j)$ if $i \neq j$
• $1 \leq x_j \leq n$
• $1 \leq y_j \leq m$

Example 1

Input:

4 6 5
7 9 8 10 
1 2 9
1 3 2
1 4 3
2 3 3
2 4 7
3 4 2
4 5
2 6
1 1
1 5
1 6

Output:

58 60 25 58 60

Example 2

Input:

10 7 10
6 2 8 8 3 9 6 5 5 9 
2 3 2
2 7 1
3 5 10
5 6 6
5 10 3
6 9 1
6 10 3
5 1
1 2
2 4
6 4
3 2
2 6
3 5
4 2
5 3
3 4

Output:

3 6 47 47 19 65 59 8 32 47