配点 : $400$ 点

問題文

長さ $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$ はクエリを処理する時点で切られていないことが保証されます。

制約

• $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$ は存在しない。
• 入力は全て整数である。

入力

入力は以下の形式で標準入力から与えられる。

$L$ $Q$

$c_1$ $x_1$

$c_2$ $x_2$

$\vdots$

$c_Q$ $x_Q$

出力

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

5 3
2 2
1 3
2 2

5
3

$1$ 番目のクエリ時点では木材は一度も切られていないので、線 $2$ を含む木材の長さは $5$ メートルです。よって $5$ を出力します。 $2$ 番目のクエリによって、木材は $3$ メートルの木材と $2$ メートルの木材に分割されます。 $3$ 番目のクエリ時点では 線 $2$ を含む木材の長さは $3$ メートルなので、$3$ を出力します。

5 3
1 2
1 4
2 3

2

100 10
1 31
2 41
1 59
2 26
1 53
2 58
1 97
2 93
1 23
2 84

69
31
6
38
38