不认识

题目背景

又是一年军训时,今年的军训有点不一样。小L和小K所在的班的同学来自五湖四海(才怪),原来互相都不认识。

题目描述

小K和小L的教官将同学们按随机顺序排成一列。教官发现所有同学互相之间竟然都不认识(小L和小K失忆了),于是教官决定让同学们互相认识一下。每次教官会令编号在闭区间$[l,r]$的所有同学两两互相认识。如果其中的一对同学在之前的操作中已经认识,那么他们不会再次认识。请问,在每次教官的操作(命令)之前,在教官指定的这个区间内有多少对同学是不认识的? 每对同学可以表示为$(u,v)[u<v]$。两对同学$(u_1,v_1)$和$(u_2,v_2)$不同当且仅当$u_1\neq u_2~or~v_1\neq v_2$。

输入输出格式

输入格式


输入第一行为一个整数$n$和$q$,$n$表示小L和小K所在的班的学生数,$q$表示教官的操作数; 之后的$q$行,每行两个整数$l'$和$r'$,表示这次操作使得闭区间$[l',r']$的所有同学两两互相认识。 本题输入加密。输入的第三行至最后一行,输入的数字都按位异或($\oplus$)了$lastans$,也就是上一个询问的输出。对于输入的第二行,你可以认为$lastans=0$。对于每个操作,你需要将$l',r'$通过某种方式解密得到真正的,即未加密过的$l,r$。

输出格式


输出共$q$行。每行对应输入中的一次操作,输出这次操作的答案。

输入输出样例

输入样例 #1

5 6
3 3
2 3
2 5
3 5
0 4
6 4

输出样例 #1

0
1
1
1
7
0

说明

样例解释: 这是解密后的输入: ``` 5 6 3 3 2 3 3 4 2 4 1 5 1 3 ``` $Subtask\#1:~20pts~,~1\le n,q \le 100$; $Subtask\#2:~30pts~,~1\le n,q\le 5000$; $Subtask\#3:~50pts~,~1\le n,q \le 10^6,1\le l,r \le n$ 保证解密后的每对$l,r$均满足$l\le r$。