題目描述
一場比賽不能沒有資料結構題,即使它只是一道氣球題。
給你一個矩陣 $M$。設矩陣第 $i$ 列第 $j$ 行的元素為 $M_{i,j}$,列數與行數分別為 $n$ 與 $m$。初始時,$n=m=1$,且 $M_{1,1}=c$。
你需要執行 $q$ 次操作,每次操作屬於以下三種類型之一:
1 x y($0\le x\le n$,$1\le y\le 10^9$)在第 $x$ 列和第 $(x+1)$ 列之間插入一列,該列所有元素的值均為 $y$;此操作後,$n$ 增加 $1$;2 x y($0\le x\le m$,$1\le y\le 10^9$)在第 $x$ 行和第 $(x+1)$ 行之間插入一行,該行所有元素的值均為 $y$;此操作後,$m$ 增加 $1$;3 x y($1\le x\le n$,$1\le y\le m$)查詢 $M_{x,y}$ 的值。
輸入格式
輸入的第一行包含兩個整數 $q,c$($1\le q\le 5\cdot 10^5$,$1\le c\le 10^9$)。
接下來的 $q$ 行,每行描述一個操作。
每行開頭的三個整數 $opt,x,y$($opt\in\{1,2,3\}$)的含義如上文所述。
輸出格式
對於每個查詢操作,輸出一行,包含一個整數,表示答案。
範例
範例輸入 1
6 1 1 0 2 3 2 1 2 1 3 1 1 4 3 2 2 3 3 2
範例輸出 1
1 4 3