As probably know, sloths live on trees. Accordingly, David has a pet sloth which he lets play on his unweighted trees when he solves programming problems. Occasionally, David will notice that his sloth is located on a particular node $a$ in the tree, and ask it to move to some other node $b$.
Of course, the sloth is as well-intentioned as can be, but alas, it only has enough energy to move across at most $c$ edges. If the sloth needs to cross fewer than $c$ edges to get to node $b$, it will get there and then take a nap. Otherwise, it will get as close as possible before it retires and hangs idly awaiting further digestion.
Where will the sloth end up? Also, since this happens quite often, David would like you to answer $q$ queries, each one of the similar form.
The first line will contain a single integer $n$, the number of nodes in the tree. The following $n -1$ lines will contain two integers $u$ and $v$, describing the edges in the tree. These edges will form a tree.
After that, there will be a single line containing an integer $q$, the number of times David will motivate his sloth to move. $q$ lines follow, each containing three integers $a$, $b$, and $c$: the node the sloth starts on, the node David asks the sloth to move to, and the energy the sloth has when starting.
$1 <= n, q <= 3 * 10^5$
$1 <= a, b, c, u, v <= n$
For each query, output a single integer: the id of the node that the sloth must sleep at.
## Input
The first line will contain a single integer $n$, the number of nodes in the tree. The following $n -1$ lines will contain two integers $u$ and $v$, describing the edges in the tree. These edges will form a tree.After that, there will be a single line containing an integer $q$, the number of times David will motivate his sloth to move. $q$ lines follow, each containing three integers $a$, $b$, and $c$: the node the sloth starts on, the node David asks the sloth to move to, and the energy the sloth has when starting.$1 <= n, q <= 3 * 10^5$$1 <= a, b, c, u, v <= n$
## Output
For each query, output a single integer: the id of the node that the sloth must sleep at.
[samples]
**Definitions**
Let $ T = (V, E) $ be an unweighted tree with $ |V| = n $.
Let $ d(u, v) $ denote the shortest path distance (number of edges) between nodes $ u $ and $ v $ in $ T $.
**Constraints**
1. $ 1 \le n, q \le 3 \cdot 10^5 $
2. For each query $ (a, b, c) $: $ 1 \le a, b, c \le n $
**Objective**
For each query $ (a, b, c) $, compute the node $ x $ where the sloth ends up:
- If $ d(a, b) \le c $, then $ x = b $.
- Otherwise, $ x $ is the unique node on the simple path from $ a $ to $ b $ at distance $ c $ from $ a $.
That is:
$$
x = \text{the node at distance } \min(c, d(a, b)) \text{ from } a \text{ along the path to } b
$$