Опис
Змагання не може обійтися без задачі на структури даних, навіть якщо це лише проста задача за кульку.
Дано матрицю $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