En una competición no puede faltar un problema de estructuras de datos, aunque solo sea un problema para conseguir un globo.

Se da una matriz $M$. Sea $M_{i,j}$ el elemento de la fila $i$ y la columna $j$, y sean $n$ y $m$ el número de filas y columnas, respectivamente. Inicialmente, $n=m=1$ y $M_{1,1}=c$.

Debes realizar $q$ operaciones, cada una de uno de los siguientes tres tipos:

• 1 x y ($0\le x\le n$, $1\le y\le 10^9$): insertar una fila de valor $y$ entre la fila $x$ y la fila $(x+1)$; después de esta operación, $n$ aumenta en $1$.

• 2 x y ($0\le x\le m$, $1\le y\le 10^9$): insertar una columna de valor $y$ entre la columna $x$ y la columna $(x+1)$; después de esta operación, $m$ aumenta en $1$.

• 3 x y ($1\le x\le n$, $1\le y\le m$): consultar el valor de $M_{x,y}$.

Entrada

La primera línea de la entrada contiene dos enteros $q,c$ ($1\le q\le 5\cdot 10^5$, $1\le c\le 10^9$).

Cada una de las siguientes $q$ líneas describe una operación.

Los tres enteros $opt,x,y$ al principio de cada línea ($opt\in\{1,2,3\}$) tienen el significado descrito en el enunciado anterior.

Salida

Para cada operación de consulta, imprime una línea con un entero que represente la respuesta.

Ejemplos

Entrada 1

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

Salida 1

1
4
3