AT_abc217_d [ABC217D] Cutting Woods

[problemUrl]: https://atcoder.jp/contests/abc217/tasks/abc217_d 長さ $ L $ メートルの直線状の木材があります。 $ x\ =\ 1,\ 2,\ \dots,\ L\ -\ 1 $ に対して、木材の左端から $ x $ メートルの地点には目印として線 $ x $ が引かれています。 $ Q $ 個のクエリが与えられます。 $ i $ 番目のクエリは数の組 $ (c_i,\ x_i) $ によって表されます。 以下の説明に従ってクエリを $ i $ の昇順に処理してください。 - $ c_i\ =\ 1 $ のとき : 線 $ x_i $ がある地点で木材を $ 2 $ つに切る。 - $ c_i\ =\ 2 $ のとき : 線 $ x_i $ を含む木材を選び、その長さを出力する。 ただし $ c_i\ =\ 1,\ 2 $ の両方に対して、線 $ x_i $ はクエリを処理する時点で切られていないことが保証されます。

入力は以下の形式で標準入力から与えられる。 > $ L $ $ Q $ $ c_1 $ $ x_1 $ $ c_2 $ $ x_2 $ $ \vdots $ $ c_Q $ $ x_Q $

$ c_i\ =\ 2 $ を満たすクエリの回数と等しい行数だけ出力せよ。 $ j $ 行目では $ j $ 番目のそのようなクエリに対する答えを出力せよ。

### 制約 - $ 1\ \leq\ L\ \leq\ 10^9 $ - $ 1\ \leq\ Q\ \leq\ 2\ \times\ 10^5 $ - $ c_i\ =\ 1,\ 2 $ $ (1\ \leq\ i\ \leq\ Q) $ - $ 1\ \leq\ x_i\ \leq\ L\ -\ 1 $ $ (1\ \leq\ i\ \leq\ Q) $ - 全ての $ i $ $ (1\ \leq\ i\ \leq\ Q) $ に対して次が成り立つ: $ 1\ \leq\ j\ \lt\ i $ かつ $ (c_j,x_j)\ =\ (1,\ x_i) $ を満たす $ j $ は存在しない。 - 入力は全て整数である。 ### Sample Explanation 1 $ 1 $ 番目のクエリ時点では木材は一度も切られていないので、線 $ 2 $ を含む木材の長さは $ 5 $ メートルです。よって $ 5 $ を出力します。 $ 2 $ 番目のクエリによって、木材は $ 3 $ メートルの木材と $ 2 $ メートルの木材に分割されます。 $ 3 $ 番目のクエリ時点では 線 $ 2 $ を含む木材の長さは $ 3 $ メートルなので、$ 3 $ を出力します。