Osu! Fruit Catching Challenge

Yuuha loves playing a game called osu!, especially the mode where you catch fruits. However, after she cleared The Big Black with DT FC, the game seemed too easy, so she invented a more challenging version.

The game is played on a tree with \( n \) vertices and \( n-1 \) edges. There are \( p \) plates on the tree, where each plate represents a unique path between two vertices and is assigned a weight. Specifically, the \( i \)-th plate is the unique path from vertex \( a_i \) to vertex \( b_i \) with weight \( c_i \).

Then, \( q \) fruits fall sequentially. Each fruit is also represented as a path from vertex \( u_i \) to vertex \( v_i \) on the tree. A plate is able to catch a fruit if and only if the plate's path is a subpath of the fruit's path; in other words, both endpoints of the plate must lie on the fruit's path.

For the \( i \)-th fruit, among all the plates that can catch it, you are required to select the plate with the \( k_i \)-th smallest weight. If there are fewer than \( k_i \) such plates, output \(-1\). Note that a plate can be used repeatedly for multiple fruits.

inputFormat

The input consists of several parts:

• The first line contains an integer \( n \) representing the number of vertices in the tree.
• The next \( n-1 \) lines each contain two integers \( u \) and \( v \), describing an edge between vertices \( u \) and \( v \).
• The next line contains an integer \( p \), the number of plates.
• The following \( p \) lines each contain three integers \( a_i \), \( b_i \), and \( c_i \), where the \( i \)-th plate is the unique path from \( a_i \) to \( b_i \) with weight \( c_i \).
• The next line contains an integer \( q \), the number of fruits.
• The final \( q \) lines each contain three integers \( u_i \), \( v_i \), and \( k_i \). This represents a fruit falling along the unique path from \( u_i \) to \( v_i \) and the requirement to choose the plate with the \( k_i \)-th smallest weight among all that can catch the fruit.

outputFormat

For each of the \( q \) fruits, output a single line. The line should contain the weight of the plate chosen (i.e. the \( k_i \)-th smallest weight among those plates that can catch the fruit), or \(-1\) if there are fewer than \( k_i \) such plates.

sample

5
1 2
1 3
3 4
3 5
3
1 3 10
2 4 5
4 5 7
4
2 4 1
2 4 2
4 5 1
1 5 2

5
10
7
-1