Feng Jian Youxiang loves playing a game called osu!, and her favorite mode is catching fruit. Since she has already achieved DT FC on The Big Black, she finds this game too simple and has invented a more difficult version.

First, there is a map, which is a tree consisting of $n$ vertices and $n-1$ edges (for example, the tree shown in Figure 1 contains 8 vertices and 7 edges). There are $P$ plates on this tree, where each plate is actually a path (for example, the path from vertex 6 to vertex 8 in Figure 1), and each plate has a weight. The $i$-th plate is the path from vertex $a_i$ to vertex $b_i$ (since it is a tree, the path from $a_i$ to $b_i$ is unique), with a weight of $c_i$.

Next, $Q$ fruits will fall one after another. Each fruit is also a path; the $i$-th fruit is the path from vertex $u_i$ to vertex $v_i$. For each fruit, Youxiang needs to choose a plate to catch it: a plate can catch a fruit if and only if the plate's path is a sub-path of the fruit's path (for example, the path from 3 to 7 in Figure 1 is a sub-path of the path from 1 to 8). It is defined here that the path from $a$ to $b$ and the path from $b$ to $a$ are the same path. To increase the difficulty, for the $i$-th fruit, you need to choose the plate with the $k_i$-th smallest weight among all plates that can catch it. Each plate can be reused (there is no upper limit on the number of times a plate can be used: after a plate catches a fruit, it can continue to catch other fruits as long as it is a sub-path of the fruit's path). Youxiang thinks this game is very difficult; can you solve it for her?

Figure 1

Input

The first line contains three integers $n$, $P$, and $Q$, representing the size of the tree, the number of plates, and the number of fruits, respectively.

The next $n-1$ lines each contain two integers $a$ and $b$, representing an edge between $a$ and $b$ in the tree. The vertices in the tree are labeled from 1 to $n$.

The next $P$ lines each contain three integers $a$, $b$, and $c$, representing a plate with the path from $a$ to $b$ and weight $c$, where $0 \le c \le 10^9$ and $a \neq b$.

The next $Q$ lines each contain three integers $u$, $v$, and $k$, representing a fruit with the path from $u$ to $v$, where $u \neq v$. You need to choose the $k$-th smallest weight among the available plates; the $k$-th smallest weight is guaranteed to exist.

Output

For each fruit, output one line representing the weight of the chosen plate.

Examples

Input 1

10 10 10
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
3 2 217394434
10 7 13022269
6 7 283254485
6 8 333042360
4 6 442139372
8 3 225045590
10 4 922205209
10 8 808296330
9 2 486331361
4 9 551176338
1 8 5
3 8 3
3 8 4
1 8 3
4 8 1
2 3 1
2 3 1
2 3 1
2 4 1
1 4 1

Output 1

442139372
333042360
442139372
283254485
283254485
217394434
217394434
217394434
217394434
217394434

Constraints

• For 20% of the data, $n, P, Q \le 3000$.
• For another 30% of the data, $n, P, Q \le 40000$, and the tree is a chain.
• For another 10% of the data, $n, P, Q \le 25000$.
• For another 10% of the data, $n, P, Q \le 30000$.
• For another 10% of the data, $n, P, Q \le 35000$.
• For another 20% of the data, $n, P, Q \le 40000$.