A contest cannot be without a data structure problem, even if it is only a ballon problem.

You are given a matrix $M$. Let the element in the $i$-th row and $j$-th column of the matrix be $M_{i,j}$, and let the number of rows and columns be $n$ and $m$, respectively. Initially, $n=m=1$, and $M_{1,1}=c$.

You need to perform $q$ operations, each of which belongs to one of the following three types:

• 1 x y ($0\le x\le n$, $1\le y\le 10^9$) insert a row with value $y$ between the $x$-th row and the $(x+1)$-th row; after this operation, $n$ increases by $1$;

• 2 x y ($0\le x\le m$, $1\le y\le 10^9$) insert a column with value $y$ between the $x$-th column and the $(x+1)$-th column; after this operation, $m$ increases by $1$;

• 3 x y ($1\le x\le n$, $1\le y\le m$) query the value of $M_{x,y}$.

Input

The first line of input contains two integers $q,c$ ($1\le q\le 5\cdot 10^5$, $1\le c\le 10^9$).

The following $q$ lines each describe one operation.

The three integers $opt,x,y$ at the beginning of each line ($opt\in\{1,2,3\}$) have the meaning described in the statement above.

Output

For each query operation, output one line containing an integer representing the answer.

Examples

Input 1

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

Output 1

1
4
3