$N$個の頂点からなる木（無向でサイクルのない連結グラフ）がある。頂点は$1$から$N$までの番号が付けられており、辺は$1$から$N-1$までの番号が付けられている。最初、すべての頂点の色は白である。

以下の2種類のクエリを実行するプログラムを作成せよ。

• 1 i: $i$番目の頂点の色を反転する。（白→黒、黒→白）
• 2: すべての白い頂点$a$と$b$について、最も遠い距離を出力する。ただし、$a$と$b$は同じでもよい。もし白い頂点が存在しない場合は$-1$を出力する。

入力

最初の行に$N$（$2 \le N \le 100{,}000$）が与えられる。

2行目から$N-1$行には、$i$番目の辺が接続する2つの頂点の番号$u$と$v$、および辺の距離$w$が与えられる。

次の行にはクエリの個数$M$（$1 \le M \le 100{,}000$）が与えられる。

次の$M$行にはクエリが1行に1つずつ与えられる。

辺の距離は常に$-1{,}000$以上、$1{,}000$以下の整数である。

出力

それぞれの$2$番目のクエリの結果を順に、1行に1つずつ出力する。

入出力例

入力 1

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

出力 1

2
2
0
-1