AT_abc426_c [ABC426C] Upgrade Required

ある OS のバージョンは $ N $ 個あり、古い順に $ 1,2,\dots,N $ の番号がついています。 PC が $ N $ 台あり、初めは $ i $ 番目の PC の OS のバージョンは $ i $ です。 $ Q $ 回の操作を順に行ってください。そのうち $ i $ 回目は次の通りです。 - 現時点での OS のバージョンが $ X_i $ かそれ以前の PC 全てを、バージョンを $ Y_i(>X_i) $ にアップグレードする。その後、この操作でアップグレードを行った PC の台数を出力する。 $ i

入力は以下の形式で標準入力から与えられる。 > $ N $ $ Q $ $ X_1 $ $ Y_1 $ $ X_2 $ $ Y_2 $ $ \vdots $ $ X_Q $ $ Y_Q $

$ Q $ 行出力せよ。 そのうち $ i $ 行目には、 $ i $ 回目の操作でアップグレードを行った PC の台数を出力せよ。

### Sample Explanation 1 この入力には $ 5 $ 回の操作が含まれます。 - はじめ、 $ 8 $ 台の PC のバージョンは $ 1,2,3,4,5,6,7,8 $ です。 - $ 1 $ 回目の操作で、バージョンが $ 2 $ かそれ以前のバージョンの PC をバージョン $ 6 $ にアップグレードします。 - この操作によって $ 2 $ 台の PC がアップグレードされ、各 PC のバージョンは $ 6,6,3,4,5,6,7,8 $ となります。 - $ 2 $ 回目の操作で、バージョンが $ 3 $ かそれ以前のバージョンの PC をバージョン $ 5 $ にアップグレードします。 - この操作によって $ 1 $ 台の PC がアップグレードされ、各 PC のバージョンは $ 6,6,5,4,5,6,7,8 $ となります。 - $ 3 $ 回目の操作で、バージョンが $ 1 $ かそれ以前のバージョンの PC をバージョン $ 7 $ にアップグレードします。 - この操作によって $ 0 $ 台の PC がアップグレードされ、各 PC のバージョンは $ 6,6,5,4,5,6,7,8 $ となります。 - $ 4 $ 回目の操作で、バージョンが $ 5 $ かそれ以前のバージョンの PC をバージョン $ 7 $ にアップグレードします。 - この操作によって $ 3 $ 台の PC がアップグレードされ、各 PC のバージョンは $ 6,6,7,7,7,6,7,8 $ となります。 - $ 5 $ 回目の操作で、バージョンが $ 7 $ かそれ以前のバージョンの PC をバージョン $ 8 $ にアップグレードします。 - この操作によって $ 7 $ 台の PC がアップグレードされ、各 PC のバージョンは $ 8,8,8,8,8,8,8,8 $ となります。 ### Constraints - 入力は全て整数 - $ 2 \le N \le 10^6 $ - $ 1 \le Q \le 2 \times 10^5 $ - $ 1 \le X_i < Y_i \le N $