002 - ghoststudents

[注意]この問題はリラクティブ問題です。入出力の方法に注意してください。

問題

うくさんはICPC部に所属しています。

ある日いつものように部活に参加していたうくさんは、部活に来ている部員の数が最初より減っていることに気づきました。

そこで、出席記録から、ある日以降（その日を含む）に一体何人が部活に参加しているのかを調べることにしました。 ただし、うくさんは適当な性格をしているので、調べている途中で新しい記録が見つかることもあります。

ICPC部員にはそれぞれ $1$ ~ $N$ までの独立な番号がつけられています。 ここで、ある日以降に部活に参加している人数を「その日以降に一度でも部活に参加した人」の数の和と定義します。

入力

$N$ $Q$
$Query_1$
$Query_2$
$:$
$Query_Q$

$1$ 行目には, 部員の数 $N$ とクエリの数 $Q(1 \le N \le 10^5, 1 \le Q \le 10^5)$ が与えられます。

つづく $Q$ 行にクエリが以下のいずれかの形で与えられます。

クエリ $1$:

$1$ $A$ $B$

クエリ $2$:

$2$ $C$

クエリ $1$ は $A$ 日目 $(1 \le A \le 10^9)$ に $B$ 番目 $(1 \le B \le N)$ の生徒が部活に参加したことを表します。

クエリ $2$ は $C$ 日目以降（$C$ 日目を含む）$(1 \le C \le 10^9)$ に出席した人数を求めたいことを表します。

クエリ $2$ が入力として与えられた場合、それに対する出力をジャッジが受け取るまで以降の入力が行われないことに注意してください。

出力

出力はクエリ $2$ の数の行からなります。

各クエリ $2$ について、$C$ 日目以降（$C$ 日目を含む）に出席した人数を $1$ 行に出力してください。

入出力例

入力例 1

4 7
2 1
1 1 1
1 2 1
2 1 
1 1 2
1 2 1
2 1

出力例 1

0
1
2

実際の動作は以下のようになります。

• ジャッジプログラムが一行目を解答プログラムのstdinに出力する。

  4 7

• ジャッジプログラムが二行目をstdoutに出力する。

  2 1

• 解答プログラムが一つ目のクエリ $2$ に対する答えを解答プログラムのstdoutに出力する。

  0

• ジャッジプログラムが三行目を解答プログラムのstdinに出力する。

  1 1 1

• ジャッジプログラムが四行目を解答プログラムのstdinに出力する。

  1 2 1

• ジャッジプログラムが五行目を解答プログラムのstdinに出力する。

  2 1

• 解答プログラムが二つ目のクエリ $2$ に対する答えを解答プログラムのstdoutに出力する。

  1

• ジャッジプログラムが六行目を解答プログラムのstdinに出力する。

  1 1 2

• ジャッジプログラムが七行目を解答プログラムのstdinに出力する。

  1 2 1

• ジャッジプログラムが八行目を解答プログラムのstdinに出力する。

  2 1

• 解答プログラムが三つ目のクエリ $2$ に対する答えを解答プログラムのstdoutに出力する。

  2

• 終了。

一つ目のクエリ $2$ に対して、出席している部員は存在しないため、答えは $0$ となります。

二つ目のクエリ $2$ に対して、出席している部員は部員 $1$ だけなので、答えは $1$ となります。

三つ目のクエリ $2$ に対して、出席している部員は部員 $1$ と部員 $2$ の二人なので、答えは $2$ となります。

四行目と八行目のように、同じ部員が同じ日に複数回出席することもあります。 部員 $3$ と部員 $4$ のように、一度も出席しない部員が存在することもあります。 解答プログラムは各クエリ $2$ に対する答えを出力したあとバッファをflushする必要があります。

解答プログラムはすべてのクエリに解答したあと直ちに終了してください。 ジャッジプログラムへの意図しない出力に対する動作は未定義となっています。

（参考までに、ジャッジ解では入出力のオーバーヘッドは $0.5$ 秒以下でした。）