Beskrivning
En tävling kan inte vara utan ett datastrukturproblem, även om det bara är ett enkelt ballongproblem.
Du får en matris $M$. Låt elementet på den $i$-te raden och $j$-te kolumnen i matrisen vara $M_{i,j}$, och låt antalet rader och kolumner vara $n$ respektive $m$. Initialt är $n=m=1$ och $M_{1,1}=c$.
Du ska utföra $q$ operationer, där var och en tillhör en av följande tre typer:
1 x y($0\le x\le n$, $1\le y\le 10^9$) infoga en rad med värdet $y$ mellan den $x$-te raden och den $(x+1)$-te raden; efter denna operation ökar $n$ med $1$;2 x y($0\le x\le m$, $1\le y\le 10^9$) infoga en kolumn med värdet $y$ mellan den $x$-te kolumnen och den $(x+1)$-te kolumnen; efter denna operation ökar $m$ med $1$;3 x y($1\le x\le n$, $1\le y\le m$) fråga efter värdet på $M_{x,y}$.
Indata
Den första raden i indata innehåller två heltal $q,c$ ($1\le q\le 5\cdot 10^5$, $1\le c\le 10^9$).
De följande $q$ raderna beskriver var och en en operation.
De tre heltalen $opt,x,y$ i början av varje rad ($opt\in\{1,2,3\}$) har den betydelse som beskrivs i problemtexten ovan.
Utdata
För varje frågeoperation, skriv ut en rad som innehåller ett heltal som representerar svaret.
Exempel
Indata 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