题目描述

现在有$n$个灯泡排成一行，分别编号$1$ ~ $n$，灯泡默认都是关闭的，而小T手速惊人，他每次可以选择一个区间$[l,r]$，然后改变这区间内的所有灯泡的状态，如果此时灯泡是打开的，则变关闭，否则从关闭变打开。现在你已经知道小T进行了$m$次操作，但小$T$想考考你，如果此时小$T$第$i$个操作不执行的话，此时多少盏灯泡是打开的。

输入格式

第一行 两个整数$n ,m$ 表示灯泡的数量和小$T$操作的次数。

接下来$m$行，每行两个整数$l,r$ 表示小$T$操作的区间。

输出格式

一行$m$个数字,每个数字之间用空格隔开，表示小$T$第$i$个操作不执行的话此时打开着的灯泡数。

样例

5 2
1 5
2 4

3 5

10 4
1 10
2 4
3 8
6 9

3 6 3 5

提示

第一个样例，当第一个操作不做时，此时只有$2,3,4$打开着，故答案为$3$，当第二个操作不做时，此时灯全部打开着，故答案为$5$。

数据范围

保证所有测试点$1\le l \le r \le n$。

对于$20\%$的数据 , 保证 $1 \le n, m \le 500$，并且每个操作中$l$和$r$都相等，即操作的都是同一段区间，不保证$l = r$。

对于$60\%$的数据 , 保证 $1 \le n, m \le 5000$。

对于 $100 \%$ 的数据，保证$1 \le n, m \le 10^6$。