题目背景

又是一年军训时，今年的军训有点不一样。小 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$。