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

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

• 1 u v: $u$ から $v$ への経路のコストを出力する。
• 2 u v k: $u$ から $v$ への経路上にある頂点のうち、$k$ 番目の頂点を出力する。$k$ は $u$ から $v$ への経路に含まれる頂点の数以下である。

入力

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

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

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

続く $M$ 行には、クエリが 1 行に 1 つずつ与えられる。

辺のコストは常に $1{,}000{,}000$ 以下の自然数である。

出力

各クエリの結果を順に 1 行に 1 つずつ出力せよ。

入出力例

入力 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

出力 1

5
3