Description

Kazami Yuuka really enjoys playing a game called osu!, and her favorite mode is catching fruits. Since she has already DT FC’d The Big Black, she thinks the game is too easy, so she invented a harder version.

First, there is a map that is a tree with $n$ vertices and $n-1$ edges.

There are $p$ plates on this tree. Each plate is actually a path, and each plate also 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 weight $c_i$.

Next, $q$ fruits will fall one by one; each fruit is essentially also a path. The $i$-th fruit is the path from vertex $u_i$ to vertex $v_i$.

Each time, Yuuka needs to choose one plate to catch the current fruit: a plate can catch a fruit if and only if the plate’s path is a subpath of the fruit’s path. By convention, the path from $a$ to $b$ is considered the same as the path from $b$ to $a$.

To increase the difficulty, for the $i$-th fruit, among all plates that can catch it, you must choose the one with the $k_i$-th smallest weight. Each plate can be reused without limit: after catching one fruit, it can continue to catch other fruits as long as it is a subpath of the fruit’s path. Yuuka thinks this game is hard; can you solve it easily for her?

Input Format

• The first line contains three integers $n$, $p$, and $q$, denoting the size of the tree, the number of plates, and the number of fruits.
• The next $n-1$ lines each contain two integers $a$ and $b$, indicating that there is an edge between $a$ and $b$ in the tree. The vertices are labeled from $1$ to $n$.
• The next $p$ lines each contain three integers $a$, $b$, and $c$, describing a plate whose path is from $a$ to $b$ with weight $c$, where $a \ne b$.
• The next $q$ lines each contain three integers $u$, $v$, and $k$, describing a fruit whose path is from $u$ to $v$, where $u \ne v$. You need to choose the $k$-th smallest plate, and the $k$-th smallest is guaranteed to exist.

Output Format

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

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

442139372 
333042360 
442139372 
283254485 
283254485 
217394434 
217394434 
217394434 
217394434 
217394434

Hint

For $100\%$ of the testdata, $1 \le n, p, q \le 4 \times 10^4$, $0 \le c \le 10^9$.

Translated by ChatGPT 5