コンテストにデータ構造の問題がないわけにはいきません。たとえ単なる風船問題でもです。

行列 $M$ が与えられます。行列の第 $i$ 行、第 $j$ 列の要素を $M_{i,j}$ とし、行数と列数をそれぞれ $n$, $m$ とします。最初は $n=m=1$、$M_{1,1}=c$ です。

$q$ 回の操作を行う必要があります。各操作は次の 3 種類のいずれかです。

• 1 x y ($0\le x\le n$, $1\le y\le 10^9$)：第 $x$ 行と第 $(x+1)$ 行の間に値 $y$ の行を挿入します。この操作の後、$n$ は $1$ 増加します。

• 2 x y ($0\le x\le m$, $1\le y\le 10^9$)：第 $x$ 列と第 $(x+1)$ 列の間に値 $y$ の列を挿入します。この操作の後、$m$ は $1$ 増加します。

• 3 x y ($1\le x\le n$, $1\le y\le m$)：$M_{x,y}$ の値を問い合わせます。

入力

入力の最初の行には 2 つの整数 $q,c$ ($1\le q\le 5\cdot 10^5$, $1\le c\le 10^9$) が含まれます。

続く $q$ 行は、それぞれ 1 つの操作を表します。

各行の先頭にある 3 つの整数 $opt,x,y$ ($opt\in\{1,2,3\}$) の意味は、上の問題文で説明したとおりです。

出力

各問い合わせ操作について、答えを表す整数を 1 行に 1 つ出力してください。

入出力例

入力 1

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

出力 1

1
4
3