AT_abc435_e [ABC435E] Cover query

$ N $ 個のマスが左右一列に並んでいます。 左から $ i $ $ (1\leq i\leq N) $ 番目のマスをマス $ i $ と呼びます。 最初、すべてのマスは白く塗られています。 $ Q $ 個のクエリが与えられるので、順に処理してください。 $ i $ $ (1\leq i\leq Q) $ 個目のクエリは次のとおりです。 > $ 2 $ つの整数 $ (L_i,R_i) $ $ (1\leq L_i\leq R_i\leq N) $ が与えられる。 > マス $ L_i, L_i+1, \ldots, R_i $ をすべて黒く塗る。 > このとき、元々白く塗られていたマスは新しく黒く塗られ、元々黒く塗られていたマスはそのままとなる。 > その後、（ $ N $ 個のマスのうち）**白く** 塗られているマスの個数を求める。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ Q $ $ L_1 $ $ R_1 $ $ L_2 $ $ R_2 $ $ \vdots $ $ L_Q $ $ R_Q $

$ Q $ 行出力せよ。 $ i $ 行目 $ (1\leq i\leq Q) $ には、 $ i $ 個目のクエリに対する答えを出力せよ。

### Sample Explanation 1 最初、 $ 10 $ 個のマスが左右一列に並んでいます。 - $ 1 $ 個目のクエリではマス $ 3,4,5 $ を黒く塗ります。操作後、白く塗られているのはマス $ 1,2,6,7,8,9,10 $ の $ 7 $ マスです。 - $ 2 $ 個目のクエリではマス $ 8,9 $ を黒く塗ります。操作後、白く塗られているのはマス $ 1,2,6,7,10 $ の $ 5 $ マスです。 - $ 3 $ 個目のクエリではマス $ 5,6,7,8 $ を黒く塗ります。操作後、白く塗られているのはマス $ 1,2,10 $ の $ 3 $ マスです。 - $ 4 $ 個目のクエリではマス $ 2,3,\ldots,9 $ を黒く塗ります。操作後、白く塗られているのはマス $ 1,10 $ の $ 2 $ マスです。 - $ 5 $ 個目のクエリではマス $ 6 $ を黒く塗ります。操作後、白く塗られているのはマス $ 1,10 $ の $ 2 $ マスです。 よって、 $ 7,5,3,2,2 $ をこの順に各行に出力します。 ### Constraints - $ 1\leq N\leq 10^9 $ - $ 1\leq Q\leq 2\times 10^5 $ - $ 1\leq L_i\leq R_i\leq N $ - 入力はすべて整数