Party

$n$ person have just entered a company, and Xiaoxun, as a supervisor, gives each of them a number from 1 to n that is not repeated.

In order to let them to get to know each other better, they would have a party every day, and there was a limit on the number of people at each party. Xiaoxun didn't want to find a way to find people randomly. So every time he had a party, he would only invite people with numbers in a certain interval to play.

The people who come to the party will get to know each other, and Xiaoxun wants to know how effective each party is. The effect is evaluated as the number of pairs of people at this party who did not appear at the same previous party.

There are mutiple test cases.

Each case starts with a line containing two integers $n,m (n\leq 5\times10^5,m\leq5\times 10^5)$which represent the number of people and the number of parties. And this is followed by $m$ lines each containing two integers $l,r(1\leq l\leq r\leq n)$ which mean the interval, and only the people whose number in the interval can take part in this party.

For each case you should print $m$ lines.

Each line containing a integer mean the effect of this party.

5 4
1 2
4 5
1 4
2 5

1
1
5
2

explaination of sample:

The first party: 1-2

The second party: 4-5

The third party: 1-3 1-4 2-3 2-4 3-4

The fourth party: 2-5 3-5

2019中山大学程序设计竞赛（重现赛）