대회에는 자료 구조 문제가 빠질 수 없습니다. 그저 풍선 문제일지라도 말입니다.

행렬 $M$이 주어집니다. 행렬의 $i$번째 행과 $j$번째 열의 원소를 $M_{i,j}$로 나타내며, 행 수와 열 수를 각각 $n$, $m$으로 나타냅니다. 처음에는 $n=m=1$이고 $M_{1,1}=c$입니다.

$q$번의 연산을 수행해야 하며, 각 연산은 다음 세 종류 중 하나입니다.

• 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}$의 값을 질의합니다.

입력

입력의 첫 번째 줄에는 두 정수 $q,c$ ($1\le q\le 5\cdot 10^5$, $1\le c\le 10^9$)가 포함됩니다.

다음 $q$개의 줄은 각각 하나의 연산을 나타냅니다.

각 줄의 시작에 있는 세 정수 $opt,x,y$ ($opt\in\{1,2,3\}$)의 의미는 위 문제 설명과 같습니다.

출력

각 질의 연산마다 답을 나타내는 정수 하나를 한 줄에 출력하세요.

예제

입력 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