$N$ 個の頂点からなる木 (無向で閉路のない連結グラフ) がある。頂点には $1$ から $N$ までの番号が、辺には $1$ から $N-1$ までの番号が付けられている。以下の 2 種類のクエリを実行するプログラムを作成せよ。

• 1 i c: i 番目の辺のコストを c に変更する。
• 2 u v: 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$ 以下の自然数である。

出力

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

入出力例

入力 1

3
1 2 1
2 3 2
3
2 1 2
1 1 3
2 1 2

出力 1

1
3