AT_abc459_c [ABC459C] Drop Blocks

$ N $ 個のマスが左右一列に並んでいます。 はじめ、すべてのマスには何も置かれていません。 $ Q $ 個のクエリが与えられるので、順に処理してください。 各クエリは次の $ 2 $ 種類のいずれかです。 - `1 x` : 左から $ x $ 番目のマスにブロックを $ 1 $ 個積む。その後、すべてのマスに $ 1 $ 個以上のブロックが積まれているならば、すべてのマスからブロックを $ 1 $ 個ずつ取り除く。 - `2 y` : $ y $ 個以上のブロックが積まれているマスの個数を出力する。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ Q $ $ \mathrm{query}_1 $ $ \mathrm{query}_2 $ $ \vdots $ $ \mathrm{query}_Q $ 各クエリ $ \mathrm{query}_i $ $ (1\leq i\leq Q) $ は次の形式のいずれかで与えられる。 > $ 1 $ $ x $ > $ 2 $ $ y $

$ 2 $ 種類目のクエリの個数を $ K $ 個として、 $ K $ 行出力せよ。 $ i $ 行目 $ (1\leq i\leq K) $ には $ i $ 番目の $ 2 $ 種類目のクエリに対する答えを出力せよ。

### Sample Explanation 1 $ N=3 $ であり、はじめ、左から $ 1,2,3 $ 番目に積まれているブロックの数は $ (0,0,0) $ です。 クエリは順に次のように処理されます。 - 左から $ 1 $ 番目のマスに $ 1 $ 個ブロックを積みます。ブロックの積まれていないマスが存在するため、それ以上の操作は行いません。左から $ 1,2,3 $ 番目に積まれているブロックの数は $ (1,0,0) $ となります。 - 左から $ 3 $ 番目のマスに $ 1 $ 個ブロックを積みます。左から $ 1,2,3 $ 番目に積まれているブロックの数は $ (1,0,1) $ となります。 - 左から $ 3 $ 番目のマスに $ 1 $ 個ブロックを積みます。左から $ 1,2,3 $ 番目に積まれているブロックの数は $ (1,0,2) $ となります。 - $ 1 $ 個以上のブロックが積まれているマスは左から $ 1 $ 番目と $ 3 $ 番目のマスの $ 2 $ つです。よって、 $ 2 $ を出力します。 - $ 2 $ 個以上のブロックが積まれているマスは左から $ 3 $ 番目のマスの $ 1 $ つだけです。よって、 $ 1 $ を出力します。 - 左から $ 2 $ 番目のマスに $ 1 $ 個ブロックを積みます。この時点ですべてのマスにブロックが $ 1 $ 個以上積まれているため、すべてのマスからブロックを $ 1 $ 個取り除きます。左から $ 1,2,3 $ 番目に積まれているブロックの数は $ (0,0,1) $ となります。 - $ 1 $ 個以上のブロックが積まれているマスは左から $ 3 $ 番目のマスの $ 1 $ つだけです。よって、 $ 1 $ を出力します。 よって、 $ 2,1,1 $ をこの順に各行に出力します。 ### Constraints - $ 1\leq N\leq 3\times 10^5 $ - $ 1\leq Q\leq 3\times 10^5 $ - $ 1\leq x\leq N $ - $ 1\leq y\leq 3\times 10^5 $ - 入力はすべて整数 - $ 2 $ 種類目のクエリが少なくとも $ 1 $ つ存在する。