Streamer Chat

問題文

配信者のmoguさんは、配信のチャット欄が連投スパムで荒らされるという被害を何度も受け、仕方なく配信サイトを変えることにしました。

とある配信サイトには、$N$ 人の視聴者がいる。(視聴者 $1 , 2 , ... ,N$ とする。)日付 $0$ までに、moguさんをフォローしている視聴者はいない。

次の $Q$ 個のクエリ($1 \leq i \leq Q$)を順に処理せよ。

• クエリ $1$ : 1 t x の形式で与えられる。日付 $t$ の初めに視聴者 $x$ がmoguさんのチャンネルをフォローする。クエリが与えられる時点で視聴者 $x$ はmoguさんのチャンネルをフォローしていないことが保証される。

• クエリ $2$ : 2 t x の形式で与えられる。日付 $t$ に視聴者 $x$ がmoguさんのチャンネルのフォローを解除する。クエリが与えられる時点で視聴者 $x$ はmoguさんのチャンネルをフォローしていることが保証される。

• クエリ $3$ : 3 t k の形式で与えられる。日付 $t$ にmoguさんが配信を行う。この際、moguさんの配信のチャット欄にチャットできるのは日付 $t-k$ の初めから日付 $t$ までの間、moguさんのチャンネルをずっとフォローしている視聴者のみである。moguさんの配信にチャットできる視聴者の人数を出力せよ。

制約

• $1 \leq N \leq 10^5$
• $1 \leq Q \leq 2 \times 10^5$
• $1 \leq t_i < t_j \leq 10^9 (1 \leq i < j \leq Q)$
• $1 \leq x_i \leq N (1 \leq i \leq Q)$
• $1 \leq k_i \leq t_i (1 \leq i \leq Q)$
• クエリ $3$ は $1$ 回以上与えられる。

入力

入力はすべて整数である。

N Q
query_1
query_2
...
query_Q

各クエリは以下のように与えられる。

1 t x

2 t x

3 t k

出力

クエリ $3$ が与えられるたびに、moguさんの配信にチャットできる視聴者の人数を $1$ 行に出力せよ。

サンプル

3 3
1 1 1
1 2 2
3 3 1

2

$1$ つ目のクエリにおいて、日付 $1$ に視聴者 $1$ がチャンネルをフォローします。 $2$ つ目のクエリにおいて、日付 $2$ に視聴者 $2$ がチャンネルをフォローします。 $3$ つ目のクエリにおいて、日付 $3$ の配信にチャットすることができるのは遅くとも日付 $3-1=2$ からずっとチャンネルをフォローしている視聴者です。 よって、視聴者 $1,2$ が配信にチャットすることができるので、 $2$ を出力します。

3 4
1 1 1
1 2 2
2 3 1
3 4 3

0

$4$ つ目のクエリにおいて、日付 $4$ の配信にチャットすることができるのは遅くとも日付 $4-3=1$ からずっとチャンネルをフォローしている視聴者です。 視聴者 $1$ は日付 $3$ にチャンネルのフォローを解除しているので、配信にチャットすることができません。 よって、誰も配信にチャットすることができないので、 $0$ を出力します。

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

1

$5$ つ目のクエリにおいて、日付 $5$ の配信にチャットすることができるのは遅くとも日付 $5-2=3$ からずっとチャンネルをフォローしている視聴者です。 視聴者 $1$ は日付 $2$ にチャンネルのフォローを解除していますが、日付 $3$ にチャンネルをフォローし、その後日付 $5$ の配信までチャンネルをフォローし続けています。 よって、視聴者 $1$ が配信にチャットすることができるので、 $1$ を出力します。