Kuvaus
Kilpailu ei voi olla ilman tietorakennetehtävää, vaikka se olisikin vain helppo ilmapallotehtävä.
Sinulle annetaan matriisi $M$. Olkoon matriisin $i$-nnen rivin ja $j$-nnen sarakkeen alkio $M_{i,j}$, ja olkoot rivien ja sarakkeiden lukumäärät $n$ ja $m$. Aluksi $n=m=1$ ja $M_{1,1}=c$.
Sinun tulee suorittaa $q$ operaatiota, joista jokainen kuuluu yhteen seuraavista kolmesta tyypistä:
1 x y($0\le x\le n$, $1\le y\le 10^9$) lisää rivi arvolla $y$ rivin $x$ ja rivin $(x+1)$ väliin; tämän operaation jälkeen $n$ kasvaa $1$:llä;2 x y($0\le x\le m$, $1\le y\le 10^9$) lisää sarake arvolla $y$ sarakkeen $x$ ja sarakkeen $(x+1)$ väliin; tämän operaation jälkeen $m$ kasvaa $1$:llä;3 x y($1\le x\le n$, $1\le y\le m$) kysy alkion $M_{x,y}$ arvoa.
Syöte
Syötteen ensimmäinen rivi sisältää kaksi kokonaislukua $q,c$ ($1\le q\le 5\cdot 10^5$, $1\le c\le 10^9$).
Seuraavat $q$ riviä kuvaavat kukin yhden operaation.
Kunkin rivin alussa olevilla kolmella kokonaisluvulla $opt,x,y$ ($opt\in\{1,2,3\}$) on yllä tehtävänannossa kuvattu merkitys.
Tuloste
Tulosta jokaiselle kyselyoperaatiolle yksi rivi, joka sisältää vastausta kuvaavan kokonaisluvun.
Esimerkit
Syöte 1
6 1 1 0 2 3 2 1 2 1 3 1 1 4 3 2 2 3 3 2
Tuloste 1
1 4 3