北海道には $N$ 店の銀行があり、$1$ から $N$ までの番号が付けられています。銀行 $1$ 以外の銀行には親銀行が存在し、銀行 $i$ $(2 \leq i \leq N)$ の親銀行は $P_i$ です。

各銀行には保管できる金額に上限があり、これをその銀行の容量とします。
銀行 $1$ は北海道一の大銀行で、その容量は $10^{100}$ 円であり、はじめ、$10^{50}$ 円を保管しています。また、銀行 $i$ $(2 \leq i \leq N)$ の容量は $C_i$ 円であり、はじめ、$A_i$ 円を保管しています。

各銀行は、お金を 引き出す または 預け入れる という要求を受けることがあります。
引き出しの要求を受けたとき、保管金額が負とならないように不足分のお金を親銀行から受け取ります。また預け入れの要求を受けたときは、容量を上回らないように余剰分のお金を親銀行へ送ります。

厳密には、引き出しまたは預け入れの要求を受けた直後、以下の操作が順に行われます。

• その時点での銀行 $i$ の保管金額を $b_i$ とする。また、要求を受けた銀行を $v$、金額を $x$ とする。引き出しの要求を受けたとき、$b_v\leftarrow b_v-x$、預け入れの要求を受けたとき、$b_v\leftarrow b_v+x$ と更新する。

• $b_i < 0$ または $b_i > C_i$ を満たす整数 $i$ が存在する限り，そのような $i$ を $1$ つ選んで以下の操作を行う。
  • $b_i < 0$ の場合、$s = -b_i$ として、銀行 $i$ と $P_{i}$ の保管金額を以下のように同時に更新する $$b_{P_i} \gets b_{P_i} - s , \quad b_{i} \gets 0$$
  • $b_i > C_i$ の場合、$s = b_i - C_i$ として、銀行 $i$ と $P_{i}$ の保管金額を以下のように同時に更新する $$b_{P_i} \gets b_{P_i} + s, \quad b_{i} \gets C_i$$

$Q$ 個のクエリが与えられるので、順に処理してください。クエリは以下の $3$ 種類のいずれかです。詳しくは入力形式を参照してください。

• 1 v x：銀行 $v$ から $x$ 円を引き出す。
• 2 v x：銀行 $v$ に $x$ 円を預け入れる。
• 3 v：銀行 $v$ の保管金額を出力する。

なお、本問題の制約下では

• 上記の操作が必ず有限回で終了し、さらに最終的な各銀行の保管金額が一意に定まること
• 銀行 $1$ の保管金額が負になることや、容量を上回ることがないこと

が示せます。

• $2 \leq N \leq 10^{5}$
• $1 \leq P_i < i$ $(2 \leq i \leq N)$
• $1 \leq C_i \leq 10^9$ $(2 \leq i \leq N)$
• $0 \leq A_i \leq C_i$ $(2 \leq i \leq N)$
• $1 \leq Q \leq 10^{5}$
• $2 \leq v \leq N$
• $1 \leq x \leq 10^9$
• 入力はすべて整数である

• set1 $(10$ 点$)$：$N \leq 1000$ かつ $Q \leq 1000$
• all $(90$ 点$)$：追加の制約はない

入力は以下の形式で標準入力から与えられます。

各クエリは以下の $3$ 種類のいずれかの形式で与えられます。

問題文の指示に従って、クエリの答えを改行区切りで出力してください。