You are playing a game on a tree.

Given a tree with $n$ nodes and $Q$ queries, for each query $(x, y, z)$, you need to find three nodes $(u, v, w)$ such that $\text{dis}(u, v) = x$, $\text{dis}(u, w) = y$, and $\text{dis}(v, w) = z$. Here, $\text{dis}(u, v)$ denotes the number of edges on the unique simple path between nodes $u$ and $v$ in the tree, and $\text{dis}(u, u) = 0$.

It is guaranteed that a solution exists.

Input

The first line contains an integer $n$, representing the number of nodes in the tree.

The next $n - 1$ lines each contain two integers $u, v$, representing an edge between $u$ and $v$.

The next line contains an integer $Q$, representing the number of queries.

The next $Q$ lines each contain three integers $x, y, z$, representing a query.

Output

Output $Q$ lines, each containing three integers $u, v, w$ such that $\text{dis}(u, v) = x$, $\text{dis}(u, w) = y$, and $\text{dis}(v, w) = z$. If there are multiple valid combinations of $(u, v, w)$, output any one of them. It is guaranteed that a solution exists.

Constraints

• For 10% of the data, $n, Q \le 500$.
• For 20% of the data, $n, Q \le 2 \times 10^3$.
• For another 20% of the data, $Q = 1$.
• For another 20% of the data, $Q \le 10$.
• For another 10% of the data, the $i$-th edge connects $i$ and $i + 1$.
• For another 10% of the data, $x = 0$.
• For 100% of the data, $1 \le n, Q \le 2 \times 10^5$, $0 \le x, y, z \le 2 \times 10^5$.

Implementation Details

A checker and checker.exe are provided for answer verification on 64-bit Linux and Windows systems, respectively.

You can use ./checker <input file> <output file> <answer file> to check if your output file is valid.

The provided checker does not actually use the answer file, so you can simply choose any file as the answer file.

You must ensure that the input file is valid (i.e., the format is correct and a solution exists), otherwise unknown errors may occur.

Depending on the issues in your output file, the checker will return the following information:

1. If your output file is correct, the checker will return "Accepted!".
2. If the answer is incorrect for the $t$-th test case, the checker will return "Wrong answer on test t!".
3. If your format is incorrect, the checker will return "wrong output format" followed by relevant error information.

Examples

Input 1

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

Output 1

2 6 1
7 6 1
9 6 6
6 2 6
6 1 7
8 6 4
9 6 1
1 2 6
6 8 6
8 6 6