題目描述
一場比賽唔可以無數據結構題,就算佢只係一道氣球題。
俾你一個矩陣 $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