Background

It is military training season again this year, and this year’s training is a bit different. The classmates in the class of Xiao L and Xiao K come from all over the country (not really), and it turns out that none of them knew each other before.

Problem Description

The instructor of Xiao K and Xiao L arranges the students into a line in a random order. The instructor finds that all students do not know each other (Xiao L and Xiao K lost their memories), so the instructor decides to let the students get to know each other.

Each time, the instructor will make all students whose indices are in the closed interval $[l,r]$ know each other pairwise. If a pair of students already knew each other from previous operations, they will not get to know each other again.

For each instructor operation (command), before performing this operation, how many pairs of students in the specified interval do not know each other?

Each pair of students can be represented as $(u,v)[u<v]$. Two pairs $(u_1,v_1)$ and $(u_2,v_2)$ are different if and only if $u_1\neq u_2~or~v_1\neq v_2$.

Input Format

The first line contains two integers $n$ and $q$. $n$ is the number of students in the class of Xiao L and Xiao K, and $q$ is the number of instructor operations.

In the following $q$ lines, each line contains two integers $l'$ and $r'$, meaning that this operation makes all students in the closed interval $[l',r']$ know each other pairwise.

The input of this problem is encrypted. From the third line to the last line, all input numbers are XORed bitwise ($\oplus$) with $lastans$, i.e., the output of the previous query. For the second line of input, you may assume $lastans=0$. For each operation, you need to decrypt $l',r'$ in some way to obtain the real (unencrypted) $l,r$.

Output Format

Output $q$ lines in total. Each line corresponds to an operation in the input, and you should output the answer for that operation.

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

0
1
1
1
7
0

Hint

Sample explanation:
This is the decrypted input:

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

It is guaranteed that after decryption, every pair $l,r$ satisfies $l\le r$.

Translated by ChatGPT 5