Read problems statements in Mandarin Chinese.

In a rooted tree, the (or LCA for short) of two vertices u and v is defined as the lowest vertex that is ancestor of both that two vertices.

Given a tree of N vertices, you need to answer the question of the form "r u v" which means if the root of the tree is at r then what is LCA of u and v.

------ Input ------

The first line contains a single integer N. Each line in the next N - 1 lines contains a pair of integer u and v representing a edge between this two vertices.

The next line contains a single integer Q which is the number of the queries. Each line in the next Q lines contains three integers r, u, v representing a query.

------ Output ------

For each query, write out the answer on a single line.

------ Constraints ------

20 points:

1 ≤ N, Q ≤ 100

40 points:

1 ≤ N, Q ≤ 10^{5}
There is less than 10 unique value of r in all queries

40 points:

1 ≤ N, Q ≤ 2 × 10^{5}

------ Example ------

Input:
4
1 2
2 3
1 4
2
1 4 2
2 4 2

Output:
1
2

------ Explanation ------

"1 4 2": if 1 is the root, it is parent of both 2 and 4 so LCA of 2 and 4 is 1.
"2 4 2": the root of the tree is at 2, according to the definition, LCA of any vertex with 2 is 2.

见题面

见题面