Beschreibung
Ein Wettbewerb darf nicht ohne eine Datenstruktur-Aufgabe stattfinden, selbst wenn es nur eine Ballon-Aufgabe ist.
Gegeben ist eine Matrix $M$. Sei das Element in der $i$-ten Zeile und $j$-ten Spalte der Matrix $M_{i,j}$, und seien die Anzahl der Zeilen und Spalten $n$ bzw. $m$. Zu Beginn gilt $n=m=1$ und $M_{1,1}=c$.
Sie müssen $q$ Operationen ausführen, von denen jede zu einem der folgenden drei Typen gehört:
1 x y($0\le x\le n$, $1\le y\le 10^9$) fügt eine Zeile mit dem Wert $y$ zwischen der $x$-ten Zeile und der $(x+1)$-ten Zeile ein; nach dieser Operation erhöht sich $n$ um $1$;2 x y($0\le x\le m$, $1\le y\le 10^9$) fügt eine Spalte mit dem Wert $y$ zwischen der $x$-ten Spalte und der $(x+1)$-ten Spalte ein; nach dieser Operation erhöht sich $m$ um $1$;3 x y($1\le x\le n$, $1\le y\le m$) fragt den Wert von $M_{x,y}$ ab.
Eingabe
Die erste Zeile der Eingabe enthält zwei ganze Zahlen $q,c$ ($1\le q\le 5\cdot 10^5$, $1\le c\le 10^9$).
Die folgenden $q$ Zeilen beschreiben jeweils eine Operation.
Die drei ganzen Zahlen $opt,x,y$ am Anfang jeder Zeile ($opt\in\{1,2,3\}$) haben die oben in der Aufgabenstellung beschriebene Bedeutung.
Ausgabe
Geben Sie für jede Abfrageoperation eine Zeile mit einer ganzen Zahl aus, die die Antwort darstellt.
Beispiele
Eingabe 1
6 1 1 0 2 3 2 1 2 1 3 1 1 4 3 2 2 3 3 2
Ausgabe 1
1 4 3