Opis
Zawody nie mogą odbyć się bez zadania na struktury danych, nawet jeśli jest to tylko zadanie balonowe.
Dana jest macierz $M$. Niech element w $i$-tym wierszu i $j$-tej kolumnie macierzy będzie oznaczony jako $M_{i,j}$, a liczba wierszy i kolumn wynosi odpowiednio $n$ oraz $m$. Początkowo $n=m=1$ oraz $M_{1,1}=c$.
Musisz wykonać $q$ operacji, z których każda należy do jednego z trzech poniższych typów:
1 x y($0\le x\le n$, $1\le y\le 10^9$) wstaw wiersz o wartości $y$ pomiędzy $x$-ty wiersz a $(x+1)$-szy wiersz; po tej operacji $n$ zwiększa się o $1$;2 x y($0\le x\le m$, $1\le y\le 10^9$) wstaw kolumnę o wartości $y$ pomiędzy $x$-tą kolumnę a $(x+1)$-szą kolumnę; po tej operacji $m$ zwiększa się o $1$;3 x y($1\le x\le n$, $1\le y\le m$) zapytaj o wartość $M_{x,y}$.
Wejście
Pierwszy wiersz wejścia zawiera dwie liczby całkowite $q,c$ ($1\le q\le 5\cdot 10^5$, $1\le c\le 10^9$).
Kolejne $q$ wierszy opisuje po jednej operacji.
Trzy liczby całkowite $opt,x,y$ na początku każdego wiersza ($opt\in\{1,2,3\}$) mają znaczenie opisane powyżej w treści zadania.
Wyjście
Dla każdej operacji zapytania wypisz jeden wiersz zawierający liczbę całkowitą oznaczającą odpowiedź.
Przykłady
Wejście 1
6 1 1 0 2 3 2 1 2 1 3 1 1 4 3 2 2 3 3 2
Wyjście 1
1 4 3