Beskrivelse
En konkurranse kan ikke være uten en datastrukturoppgave, selv om det bare er en enkel ballongoppgave.
Du får gitt en matrise $M$. La elementet i den $i$-te raden og $j$-te kolonnen i matrisen være $M_{i,j}$, og la antallet rader og kolonner være henholdsvis $n$ og $m$. Til å begynne med er $n=m=1$, og $M_{1,1}=c$.
Du må utføre $q$ operasjoner, som hver tilhører én av følgende tre typer:
1 x y($0\le x\le n$, $1\le y\le 10^9$) sett inn en rad med verdi $y$ mellom den $x$-te raden og den $(x+1)$-te raden; etter denne operasjonen øker $n$ med $1$;2 x y($0\le x\le m$, $1\le y\le 10^9$) sett inn en kolonne med verdi $y$ mellom den $x$-te kolonnen og den $(x+1)$-te kolonnen; etter denne operasjonen øker $m$ med $1$;3 x y($1\le x\le n$, $1\le y\le m$) spør etter verdien av $M_{x,y}$.
Inndata
Den første linjen i inndata inneholder to heltall $q,c$ ($1\le q\le 5\cdot 10^5$, $1\le c\le 10^9$).
De følgende $q$ linjene beskriver hver én operasjon.
De tre heltallene $opt,x,y$ på begynnelsen av hver linje ($opt\in\{1,2,3\}$) har betydningen beskrevet i oppgaveteksten ovenfor.
Utdata
For hver spørreoperasjon skal du skrive ut én linje som inneholder et heltall som representerer svaret.
Eksempler
Inndata 1
6 1 1 0 2 3 2 1 2 1 3 1 1 4 3 2 2 3 3 2
Utdata 1
1 4 3