Yi is one of many hardworking truck drivers in a mysterious land. In this mysterious land, there are ~N~ villages connected by ~N-1~ two-way roads. His job, like many others, is to transport mysterious substances from one village to another through these roads. Each village can travel to any other village using these roads. At each village, there is a population of ~p_i~ residents.

Yi has ~Q~ trips. For each trip, he must travel from village ~a~ to village ~b~. He wants to find the first village on the path from ~a~ to ~b~ where the population is greater than or equal to ~k~ (including village ~a~). If there are no villages with a population greater than or equal to ~k~, or if it is impossible to travel between village ~a~ and village ~b~ (more to follow in the next paragraph), print -1.

Truck drivers, as it turns out, are not always very careful (unlike Yi). Sometimes, after Yi is finished his ~x^{th}~ trip, and before his ~x+1^{th}~, the mysterious substance that the other truck driver is carrying will spill onto road ~y~, permanently destroying road ~y~ for any of Yi's subsequent trips (In particular, trip ~x+1~ to trip ~Q~). This will happen ~R~ times. Note that this may render future trips to be impossible for Yi, in which case -1 should be outputted for those trips.

Input Specification

The first line will contain three integers, ~N, Q, R~ ~(1 \le N \le 10^5, 1 \le Q \le 10^5, 0 \le R < N)~.

The second line will contain ~N~ integers, ~p_1, p_2, \dots, p_N~ ~(0 \le p_i \le 10^9)~, the population of each village.

The next ~N-1~ lines will each contain two integers, ~u_i, v_i~ ~(1 \le u_i, v_i \le N)~, meaning that there is a road connecting village ~u_i~ and village ~v_i~.

The next ~R~ lines will each contain two integers, ~x, y~ ~(1 \le x \le Q, 1 \le y < N)~. This means that the ~y^{th}~ road (from the order in the input) is destroyed immediately after Yi's ~x^{th}~ trip. It is guaranteed that ~y~ is unique, however it is not guaranteed that ~x~ is unique.

The next ~Q~ lines will each contain a trip of the form a b k ~(1 \le a, b \le N, 0 \le k \le 10^9)~.

Output Specification

For each trip, output the first village on the path from ~a~ to ~b~ where the population is greater than or equal to ~k~ (including village ~a~). If there is no path from ~a~ to ~b~, or if no village has a population greater than or equal to ~k~ on the path, print -1.

Constraints

Subtask 1 [5%]

~N, Q \le 100~

~R = 0~

Subtask 2 [35%]

~R = 0~

Subtask 3 [60%]

No additional constraints.

Sample Input 1

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

Sample Output 1

2
1
-1
6
1
8
-1
2

Sample Input 2

9 5 2
100 0 3 0 7 5 1 0 2
1 2
2 3
1 4
4 5
4 6
6 7
6 8
6 9
4 1
3 3
2 9 2
3 6 1
7 1 99
4 2 6
3 6 1

Sample Output 2

1
3
1
-1
-1