Deskripsi
Sebuah kontes tidak boleh tanpa soal struktur data, meskipun itu hanya soal pembagian balon.
Anda diberikan sebuah matriks $M$. Misalkan elemen pada baris ke-$i$ dan kolom ke-$j$ dari matriks adalah $M_{i,j}$, dan misalkan banyaknya baris dan kolom masing-masing adalah $n$ dan $m$. Pada awalnya, $n=m=1$, dan $M_{1,1}=c$.
Anda perlu melakukan $q$ operasi, yang masing-masing termasuk dalam salah satu dari tiga jenis berikut:
1 x y($0\le x\le n$, $1\le y\le 10^9$) sisipkan sebuah baris dengan nilai $y$ di antara baris ke-$x$ dan baris ke-$(x+1)$; setelah operasi ini, $n$ bertambah sebesar $1$;2 x y($0\le x\le m$, $1\le y\le 10^9$) sisipkan sebuah kolom dengan nilai $y$ di antara kolom ke-$x$ dan kolom ke-$(x+1)$; setelah operasi ini, $m$ bertambah sebesar $1$;3 x y($1\le x\le n$, $1\le y\le m$) tanyakan nilai dari $M_{x,y}$.
Masukan
Baris pertama masukan berisi dua bilangan bulat $q,c$ ($1\le q\le 5\cdot 10^5$, $1\le c\le 10^9$).
$q$ baris berikutnya masing-masing menjelaskan satu operasi.
Tiga bilangan bulat $opt,x,y$ di awal setiap baris ($opt\in\{1,2,3\}$) memiliki arti sebagaimana dijelaskan pada pernyataan di atas.
Keluaran
Untuk setiap operasi pertanyaan, keluarkan satu baris yang berisi sebuah bilangan bulat yang menyatakan jawabannya.
Contoh
Masukan 1
6 1 1 0 2 3 2 1 2 1 3 1 1 4 3 2 2 3 3 2
Keluaran 1
1 4 3