Gardening

You are given a tree with $N$ vertices. Here, a tree is an undirected graph in which any two vertices are connected by exactly one simple path, or equivalently a connected acyclic undirected graph. A tree with $N$ vertices, contains exactly $N - 1$ undirected edges.

You have to process $Q$ queries. In each of the query, you will be given 3 positive integers $R$, $U$and $V$. You have to perform the following operations on your tree —

• Add an edge between $U$ and $V$.

• Remove an edge such that the resulting graph is still a tree. You can also remove the newly added edge.

• Minimize the sum of distance of every vertex from the vertex $R$. Formally , let $d_i$ denote the shortest distance from vertex $R$ to vertex $i$. You have to minimize $\sum_{1\le i\le n}^{} d_i$

• Print the Minimized Sum

Note that, Each query is independent which means operations in one query does not affect the other queries.

Input

The first line of the input will contain an integer, $N$ $(2 \leq N \leq 3 \times 10^5)$ which denotes the number of vertices of the tree.

Each of the next $N - 1$ lines will contain $2$ space-separated integers $u_i$ and $v_i$$(1 \leq u_i, v_i \leq N)$, indicating an edge between vertices $u_i$ and $v_i$. It is guaranteed that the given edges form a tree.

The next line will contain an integer $Q$ $(1\leq Q\leq 3\times 10 ^ 5)$, the number of queries.

Finally, each of the next $Q$ line will contain $3$ integers $R_i$,$U_i$ and $V_i$$(1 \leq R_i, U_i, V_i \leq N)$ — representing each query.

Output

Print the answer for each query in separate lines.

Samples

Input	Output
5 2 1 3 1 4 3 5 1 4 4 2 1 2 1 2 4 2 1 4 4 1	9 8 9 6

Input	Output
6 1 2 2 3 3 4 4 6 1 5 2 1 5 6 1 5 4	9 9

Input	Output
10 2 1 3 2 4 3 5 3 6 4 7 2 8 4 9 8 10 7 2 1 10 4 9 1 9	27 23