問題
$N \ $個の機械がある。以下のような2種類のクエリが$ \ Q \ $個与えられるので順に処理せよ。また、各クエリを処理した後に現在電源がオンである機械の個数を出力せよ。
1 l r:$ \ l \ $番目から$ \ r \ $番目までの機械で電源がオンであるもののうち、最後に使用した機械を使用する。そのような機械が無い場合、$l \ $番目の機械の電源をオンにし使用する。2 l r:$ \ l \ $番目から$ \ r \ $番目までの機械の電源をオフにする。
ただし、はじめ全ての機械の電源はオフである。
入力
入力は以下の形式で標準入力から与えられる。
$N \ Q$ $Query_1$ $Query_2$ $\vdots$ $Query_Q$
各クエリは以下のいずれかの形式で与えられる。
$1 \ l \ r$
$2 \ l \ r$
出力
出力は$ \ Q \ $行からなる。$i \ $行目には$ \ i \ $番目までのクエリを処理した直後に電源がオンである機械の個数を出力せよ。
制約
全ての入出力ケースについて以下を満たす。
- $1 \leq N, Q \leq 3 \times 10^5$
- $1 \leq l \leq r \leq N$
- 入力は全て整数
入出力例
入力例
5 5 1 1 3 1 3 5 1 1 3 2 3 5 1 1 5
出力例
1 2 2 1 1
- $1 \ $番目から$ \ 3 \ $番目までの機械の電源は全てオフなので$ \ 1 \ $番目の機械の電源をオンにし使用する。
- $3 \ $番目から$ \ 5 \ $番目までの機械の電源は全てオフなので$ \ 3 \ $番目の機械の電源をオンにし使用する。
- $1 \ $番目から$ \ 3 \ $番目までの機械のうち$ \ 1 \ $番目と$ \ 3 \ $番目の機械の電源がオンである。このうち最後に使用したのは$ \ 3 \ $番目の機械なのでこの機械を使用する。
- $3 \ $番目から$ \ 5 \ $番目までの機械の電源をオフにする。
- $1 \ $番目から$ \ 5 \ $番目までの機械のうち$ \ 1 \ $番目の機械の電源だけがオンなのでこの機械を使用する。