JOI 国には N 個の街があり，街には 1 から N までの番号が付けられている． これらの街の間を結ぶ N-1 本の 一方通行 の道路がある． 具体的には，各 i = 2, 3, \ldots, N について，街 i から街 P_i に向かう道路がある． ここで，1 \leqq P_i < i が保証される．

N 個の街にはそれぞれ 危険度 が定義されている． 首都である街 1 の危険度は 0 である． 街 i (2\leqq i \leqq N) の危険度は，街 i から街 1 へ向かう経路において通る道路の本数として定義される． ここで，JOI 国の構造上，街 i から街 1 へ向かう経路はちょうど 1 つ存在することに注意せよ．

現在街 i (1\leqq i \leqq N) には K_i 匹のビーバーが住んでいる． JOI 国の大統領であるビ太郎はビーバーたちの移住計画を立てた． 移住計画はこれから Q 日間にわたって実行される． j 日目 (1\leqq j \leqq Q) には次の 3 種類のうちいずれか 1 つのイベントが発生する．

• 移住
  その時点で危険度 X_j の街に住んでいるビーバー全員が，各々が住んでいる街から何本かの道路を通ってたどり着くことのできる危険度 Y_j の街へ移住する．ここで，0\leqq Y_j < X_j が保証される．JOI 国の構造上，各ビーバーについて，移住先が一意に定まることに注意せよ．

• 移民受け入れ
  JOI 国外からの移民を受け入れることで，街 A_j に住むビーバーの数が L_j だけ増加する．

• 調査
  その時点で街 B_j に住んでいるビーバーの数を調査する．

ビ太郎の部下であるあなたは，各調査イベントにおいて実際にその街を訪れなくとも移住計画の情報のみによってビーバーの数を計算できることに気づいた．

JOI 国の構造，現在住んでいるビーバーの数，および移住計画についての情報が与えられたとき，各調査イベントの結果を計算するプログラムを作成せよ．

制約

• 2 \leqq N \leqq 2\,000\,000．
• 1 \leqq P_i < i (2 \leqq i \leqq N)．
• 0 \leqq K_i \leqq 100 (1 \leqq i \leqq N)．
• 1 \leqq Q \leqq 2\,000\,000．
• T_j は 1, 2, 3 のいずれかである (1\leqq j \leqq Q)．
• T_j=1 のとき，0 \leqq Y_j < X_j \leqq N-1 (1\leqq j \leqq Q)．
• T_j=2 のとき，1\leqq A_j \leqq N，1 \leqq L_j \leqq 100 (1\leqq j \leqq Q)．
• T_j=3 のとき， 1 \leqq B_j \leqq N (1\leqq j \leqq Q)．
• T_j=3 となる j (1\leqq j \leqq Q) が 1 つ以上存在する．
• 入力される値はすべて整数である．

小課題

街の危険度の最大値を D とする．

1. (4 点) D = 1．
2. (8 点) N \leqq 20．
3. (13 点) D\leqq 20．
4. (15 点) T_j\neq 2 (1\leqq j\leqq Q)．さらに，T_j = 3 となる j (1\leqq j\leqq Q) の個数は 5 以下．
5. (15 点) T_j = 3 となる j (1\leqq j\leqq Q) の個数は 5 以下．
6. (27 点) T_j\neq 2 (1\leqq j\leqq Q)．
7. (18 点) 追加の制約はない．

入力例 1

4
1 1 2
1 3 4 3
6
3 1
1 1 0
3 1
3 2
1 2 1
3 2

出力例 1

1
8
0
3

最初，街 1,2,3,4 にはそれぞれ 1,3,4,3 匹のビーバーが住んでいる． また，各街の危険度はそれぞれ 0,1,1,2 である．

1 日目は調査イベントが発生する． したがって，1 行目にはその時点で街 1 に住むビーバーの数である 1 を出力する．

2 日目は移住イベントが発生する． その時点で街 2 に住んでいるビーバーは街 1 に移動する． また，その時点で街 3 に住んでいるビーバーも街 1 に移動する． 2 日目の終了時点で，街 1,2,3,4 にはそれぞれ 8,0,0,3 匹のビーバーが住んでいる．

3 日目は調査イベントが発生する． したがって，2 行目にはその時点で街 1 に住むビーバーの数である 8 を出力する．

4 日目は調査イベントが発生する． したがって，3 行目にはその時点で街 2 に住むビーバーの数である 0 を出力する．

5 日目は移住イベントが発生する． その時点で街 4 に住んでいるビーバーは街 2 に移動する． 5 日目の終了時点で，街 1,2,3,4 にはそれぞれ 8,3,0,0 匹のビーバーが住んでいる．

6 日目は調査イベントが発生する． したがって，4 行目にはその時点で街 2 に住むビーバーの数である 3 を出力する．

この入力例は小課題 2,3,4,5,6,7 の制約を満たす．

入力例 2

3
1 1
3 1 4
11
2 2 5
1 2 0
3 1
1 1 0
3 1
3 2
2 3 4
3 3
1 1 0
3 3
3 1

出力例 2

3
13
0
4
0
17

最初，街 1,2,3 にはそれぞれ 3,1,4 匹のビーバーが住んでいる． また，各街の危険度はそれぞれ 0,1,1 である．

1 日目は移民受け入れイベントが発生する． 街 2 に住むビーバーの数が 5 だけ増える． 1 日目の終了時点で，街 1,2,3 にはそれぞれ 3,6,4 匹のビーバーが住んでいる．

2 日目は移住イベントが発生する． その時点で危険度が 2 の街に住んでいるビーバーはいないため，移動は起こらない．

3 日目は調査イベントが発生する． したがって，1 行目にはその時点で街 1 に住むビーバーの数である 3 を出力する．

4 日目は移住イベントが発生する． その時点で街 2 に住んでいるビーバーは街 1 に移動する． また，その時点で街 3 に住んでいるビーバーも街 1 に移動する． 4 日目の終了時点で，街 1,2,3 にはそれぞれ 13,0,0 匹のビーバーが住んでいる．

5 日目は調査イベントが発生する． したがって，2 行目にはその時点で街 1 に住むビーバーの数である 13 を出力する．

6 日目は調査イベントが発生する． したがって，3 行目にはその時点で街 2 に住むビーバーの数である 0 を出力する．

7 日目以降も同様にイベントが発生するが，ここでは説明を省略する．

この入力例は小課題 1,2,3,7 の制約を満たす．

入力例 3

7
1 2 1 3 3 2
5 2 8 9 4 0 5
10
1 3 1
2 4 10
3 2
1 6 3
1 2 0
3 1
3 4
2 5 6
3 5
3 3

出力例 3

6
18
19
6
0

この入力例は小課題 2,3,5,7 の制約を満たす．