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