题目背景

又是一年军训时，今年的军训有点不一样。小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$行。每行对应输入中的一次操作，输出这次操作的答案。

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

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$。