004 - ghoststudents2

問題

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

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

そこで、出席記録から、ある期間に一体何人が部活に参加しているのかを調べることにしました。 ただし、うくさんは適当な性格をしているので、調べている途中で新しい記録が見つかることもあります。 その場合でも気にせずその時点で確定している出席人数を求めることにします。

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

入力

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

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

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

クエリ $1$:

$1$ $A$ $B$

クエリ $2$:

$2$ $C$ $D$

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

クエリ $2$ は $C$ 日目から $D$ 日目 $(1 \le C \le D \le 10^6)$ の間に出席した人数を求めたいことを表します。

出力

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

各クエリ $2$ について、$C$ 日目から $D$ 日目の間に出席した人数を $1$ 行に出力してください。

入出力例

入力例 1

4 5
1 1 1
1 2 1
2 1 2
1 1 2
2 1 2

出力例 1

1
2

入力例 2

5 8
1 1 1
1 1 1
1 2 2
1 3 3
1 4 4
1 5 5
2 1 5
2 2 3

出力例 2

5
2

同じ部員が同じ日に複数回出席することもあります。