Busy Beaver はデータ構造の問題が好きですが、配列に対する区間クエリを扱うデータ構造の問題は退屈だと考えています。そこで彼は、多重集合（multiset）を用いた一風変わったデータ構造の問題を考案しました。

$a_1, \dots, a_L$ という数列があり、各 $a_i$ は正の整数の多重集合です。最初、数列は空であり、$L=0$ です。以下の操作を実装してください。

• 1 M K: 数 $M$ が $K$ 個含まれる多重集合を数列の末尾に追加する。
• 2 X Y: $a_X$ と $a_Y$ の和を数列の末尾に追加する。各値の出現回数が加算されます。例えば、多重集合 $\{1, 1, 2\}$ と $\{1, 2\}$ の和は $\{1, 1, 1, 2, 2\}$ と定義されます。
• 3 X M K: $f(a_X, M, K)$ を数列の末尾に追加する。ここで $f(S, M, K)$ は、$S$ に $M$ が $K$ 個以上含まれる場合は $S$ から $M$ を $K$ 個取り除いたもの、そうでない場合は $S$ に $M$ を $K$ 個追加したものとして定義される。
• 4 X: $a_X$ は単一の要素のみからなることが保証される。 この $a_X$ の単一の要素を出力する。

入力

入力の最初の行には、操作の回数を表す整数 $Q$ ($1 \le Q \le 5 \cdot 10^5$) が与えられます。

続く $Q$ 行には、各操作が記述されています。

以下のことが保証されます。

• 操作 2, 3, 4 で使用されるインデックス $X$ および $Y$ は、操作時点で常に数列の範囲内である。
• 操作 1 および 3 で使用される値 $M$ および $K$ は、$1 \le M, K \le 10^9$ を満たす。
• すべてのタイプ 4 の操作において、$a_X$ はちょうど 1 つの要素を含む。

出力

各タイプ 4 の操作について、答えを 1 行で出力してください。

小課題

• ($10$ 点) すべてのタイプ 1 および 3 の操作において $1 \le M \le 10$。
• ($40$ 点) すべてのタイプ 3 の操作において、新しく追加される多重集合は $a_X$ から $M$ を $K$ 個取り除くことで形成されることが保証される。
• ($50$ 点) 追加の制約はない。

入出力例

入力 1

8
1 5 1
1 6 2
4 1
2 1 2
3 3 6 4
3 4 6 5
3 5 5 1
4 6

出力 1

5
6

注記

多重集合は以下の通りです。

• $a_1 = \{5\}$
• $a_2 = \{6, 6\}$
• $a_3 = \{5, 6, 6\}$
• $a_4 = \{5, 6, 6, 6, 6, 6, 6\}$
• $a_5 = \{5, 6\}$
• $a_6 = \{6\}$