Описание
Соревнование не может обойтись без задачи на структуры данных, даже если это всего лишь задача за шарик.
Дана матрица $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$) вставить строку со значением $y$ между $x$-й строкой и $(x+1)$-й строкой; после этой операции $n$ увеличивается на $1$;2 x y($0\le x\le m$, $1\le y\le 10^9$) вставить столбец со значением $y$ между $x$-м столбцом и $(x+1)$-м столбцом; после этой операции $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