Lýsing
Keppni getur ekki verið án gagnagrindardæmis, jafnvel þótt það sé bara einfalt blöðrudæmi.
Gefið er fylki $M$. Látum stakið í $i$-tu röð og $j$-ta dálki fylkisins vera $M_{i,j}$, og látum fjölda raða og dálka vera $n$ og $m$, í sömu röð. Í upphafi er $n=m=1$ og $M_{1,1}=c$.
Þú þarft að framkvæma $q$ aðgerðir, þar sem hver þeirra tilheyrir einni af eftirfarandi þremur gerðum:
1 x y($0\le x\le n$, $1\le y\le 10^9$) settu inn röð með gildinu $y$ á milli $x$-tu raðarinnar og $(x+1)$-tu raðarinnar; eftir þessa aðgerð hækkar $n$ um $1$;2 x y($0\le x\le m$, $1\le y\le 10^9$) settu inn dálk með gildinu $y$ á milli $x$-ta dálksins og $(x+1)$-ta dálksins; eftir þessa aðgerð hækkar $m$ um $1$;3 x y($1\le x\le n$, $1\le y\le m$) spurðu um gildið á $M_{x,y}$.
Inntak
Fyrsta línan í inntakinu inniheldur tvær heiltölur $q,c$ ($1\le q\le 5\cdot 10^5$, $1\le c\le 10^9$).
Næstu $q$ línur lýsa hver um sig einni aðgerð.
Heiltölurnar þrjár $opt,x,y$ í upphafi hverrar línu ($opt\in\{1,2,3\}$) hafa þá merkingu sem lýst er í dæmatextanum hér að ofan.
Úttak
Fyrir hverja fyrirspurnaraðgerð skal prenta eina línu sem inniheldur heiltölu sem táknar svarið.
Dæmi
Inntak 1
6 1 1 0 2 3 2 1 2 1 3 1 1 4 3 2 2 3 3 2
Úttak 1
1 4 3