問題

背景

趣味の盆栽に没頭しているイクタ君は、枝の切り方と肥料の与え方を工夫し、上手に盆栽を作ることが可能である。 イクタ君は肥料の与え方がとてもうまいので、特定の枝を太くしたり、細くしたりできる。 (この盆栽の枝は次元を超越しており太さが負になりうることに注意してほしい。)
また、ある盆栽が大きすぎると思った時はその盆栽の枝のうち最も細い(太さの値が最も低い)枝を切って、木を 2 つに分け、切り取って別れた木はまた鉢に植え、新たな盆栽とする。 あなたは、イクタ君が盆栽を育てる計画をもとに、枝を切る操作でどの枝を切るかを特定することにした。

課題

木が与えられる。木の辺にはそれぞれ整数の強度が与えられている。
この木に対して、次のクエリを処理せよ。

• クエリ1: 辺 i , 整数 d が与えられる。辺iの強度を d だけ増加させる。辺 i が既に削除されている場合は何もしない。
• クエリ2: 辺 i が与えられる。辺 i を含む連結成分を構成する辺のうち、一番強度の低い辺 j を一行で出力した後、辺 j を削除する(強度が最低のものが複数の場合は、辺の番号が最小のものを削除する。) 辺 i が既に削除されている場合は -1 を出力せよ。

配点

300

入力

入力は以下の形式で与えられる。

N
a_1 b_1 c_1
:
a_{N-1} b_{N-1} c_{N-1}
Q
q_1
:
q_Q

入力の 1 行目に木の頂点数を表す整数Nが与えられる。
続く N-1 行に頂点 a_i, b_i とそれらを結ぶ辺の初期強度 c_i を表す 3 つの整数が与えられる。
N+1 行目に処理すべきクエリの数 Q 、続く Q 行にクエリの内容が以下のように書かれている
クエリ 1 は

1 i d

クエリ 2 は

2 i

が i が辺の番号(入力の i 番目の辺)、 d は強度を表すという形で入力される。

制約

• 2 ≤ N ≤ 100,000
• 1 ≤ a_i, b_i ≤ N
• -100,000 ≤ c_i ≤ 100,000
• 1 ≤ Q ≤ 100,000
• 1 ≤ i ≤ N-1
• -10,000 ≤ d ≤ 10,000
• 入力で与えられるグラフは木になっている。

部分点

この問題には部分点が設定されている。この問題のテストケースのうち 30 点分は追加で以下の制約を満たす。

• 2 ≤ N ≤ 1,000
• 1 ≤ Q ≤ 1,000

出力

クエリ2に対する答えをそれぞれ一行で出力せよ。

---

入力例1

5
1 3 3
2 3 3
3 4 3
4 5 3
7
1 2 4
1 1 1
1 3 -1
2 1
2 1
2 1
2 4

出力例1

3
1
-1
4

---

入力例2

6
2 1 -2
3 2 0
4 1 -1
5 4 0
6 2 0
6
2 4
2 3
2 4
1 2 4
1 2 0
2 3

出力例2

1
3
4
-1