There is a tree (undirected connected graph without cycles) consisting of $N$ vertices. The vertices are numbered from $1$ to $N$, and the edges are numbered from $1$ to $N-1$.

Write a program that performs the following two types of queries:

• 1 u v: Output the cost of the path from $u$ to $v$.
• 2 u v k: Output the $k$-th vertex on the path from $u$ to $v$. Here, $k$ is less than or equal to the number of vertices on the path from $u$ to $v$.

Input

The first line contains $N$ ($2 \le N \le 100\,000$).

The next $N-1$ lines each contain two vertex numbers $u$ and $v$ connected by edge $i$, and the cost $w$ of that edge.

The next line contains the number of queries $M$ ($1 \le M \le 100\,000$).

The next $M$ lines each contain a query.

The cost of an edge is always a natural number less than or equal to $1\,000\,000$.

Output

For each query, output the result on a separate line in order.

Examples

Input 1

6
1 2 1
2 4 1
2 5 2
1 3 1
3 6 2
2
1 4 6
2 4 6 4

Output 1

5
3