AT_abc426_c [ABC426C] Upgrade Required

There are $ N $ versions of a certain OS, numbered $ 1,2,\dots,N $ in chronological order. There are $ N $ PCs, and initially the OS version of the $ i $ -th PC is $ i $ . Perform $ Q $ operations in order. The $ i $ -th operation is as follows: - Upgrade all PCs whose current OS version is $ X_i $ or earlier to version $ Y_i(>X_i) $ . Then, print the number of PCs upgraded in this operation. Note that for $ i

The input is given from Standard Input in the following format: > $ N $ $ Q $ $ X_1 $ $ Y_1 $ $ X_2 $ $ Y_2 $ $ \vdots $ $ X_Q $ $ Y_Q $

Output $ Q $ lines. The $ i $ -th line should contain the number of PCs upgraded in the $ i $ -th operation.

### Sample Explanation 1 This input contains five operations. - Initially, the versions of the eight PCs are $ 1,2,3,4,5,6,7,8 $ . - In the first operation, PCs with version $ 2 $ or earlier are upgraded to version $ 6 $ . - This operation upgrades two PCs, and the versions of the PCs become $ 6,6,3,4,5,6,7,8 $ . - In the second operation, PCs with version $ 3 $ or earlier are upgraded to version $ 5 $ . - This operation upgrades one PC, and the versions of the PCs become $ 6,6,5,4,5,6,7,8 $ . - In the third operation, PCs with version $ 1 $ or earlier are upgraded to version $ 7 $ . - This operation upgrades zero PCs, and the versions of the PCs become $ 6,6,5,4,5,6,7,8 $ . - In the fourth operation, PCs with version $ 5 $ or earlier are upgraded to version $ 7 $ . - This operation upgrades three PCs, and the versions of the PCs become $ 6,6,7,7,7,6,7,8 $ . - In the fifth operation, PCs with version $ 7 $ or earlier are upgraded to version $ 8 $ . - This operation upgrades seven PCs, and the versions of the PCs become $ 8,8,8,8,8,8,8,8 $ . ### Constraints - All input values are integers. - $ 2 \le N \le 10^6 $ - $ 1 \le Q \le 2 \times 10^5 $ - $ 1 \le X_i < Y_i \le N $