Descrizione
Una gara non può fare a meno di un problema sulle strutture dati, anche se è solo un problema palloncino.
Ti viene data una matrice $M$. Sia $M_{i,j}$ l'elemento nella $i$-esima riga e $j$-esima colonna della matrice, e siano $n$ e $m$ rispettivamente il numero di righe e di colonne. Inizialmente, $n=m=1$, e $M_{1,1}=c$.
Devi eseguire $q$ operazioni, ciascuna delle quali appartiene a uno dei seguenti tre tipi:
1 x y($0\le x\le n$, $1\le y\le 10^9$) inserisci una riga con valore $y$ tra la $x$-esima riga e la $(x+1)$-esima riga; dopo questa operazione, $n$ aumenta di $1$;2 x y($0\le x\le m$, $1\le y\le 10^9$) inserisci una colonna con valore $y$ tra la $x$-esima colonna e la $(x+1)$-esima colonna; dopo questa operazione, $m$ aumenta di $1$;3 x y($1\le x\le n$, $1\le y\le m$) chiedi il valore di $M_{x,y}$.
Input
La prima riga dell'input contiene due interi $q,c$ ($1\le q\le 5\cdot 10^5$, $1\le c\le 10^9$).
Le successive $q$ righe descrivono ciascuna un'operazione.
I tre interi $opt,x,y$ all'inizio di ciascuna riga ($opt\in\{1,2,3\}$) hanno il significato descritto nel testo sopra.
Output
Per ciascuna operazione di query, stampa una riga contenente un intero che rappresenta la risposta.
Esempi
Input 1
6 1 1 0 2 3 2 1 2 1 3 1 1 4 3 2 2 3 3 2
Output 1
1 4 3