There is a tree (an undirected connected acyclic graph) with $N$ vertices. The vertices are numbered $1$ to $N$, and the edges are numbered $1$ to $N-1$. Initially, all vertices are white.

Write a program that processes the following two queries:

• 1 i: Toggle the color of vertex $i$ (white -> black, black -> white).
• 2: For all white vertices $a$ and $b$, output the maximum distance. Here, $a$ and $b$ may be the same vertex. If there is no white vertex, output $-1$.

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 the $i$-th edge, and the edge weight $w$.

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

The following $M$ lines each contain one query.

Edge weights are always integers greater than or equal to $-1\,000$ and less than or equal to $1\,000$.

Output

For each type 2 query, output the result in order, one per line.

Examples

Input 1

3
1 2 1
1 3 1
7
2
1 1
2
1 2
2
1 3
2

Output 1

2
2
0
-1