Introducing Acquaintance Pairs

There are n students standing in a random order. Initially, no two students know each other. A coach then performs m operations. In each operation, the coach selects an interval \([l, r]\) and makes every pair of students in that interval acquainted with one another. If a pair has already been acquainted by a previous operation, they will not be introduced again.

For every operation, before applying the changes, you are to determine the number of pairs \((u,v)\) (with \(u < v\)) in the interval \([l, r]\) that do not know each other. After that, the acquaintance relation for all pairs in \([l, r]\) will be updated.

Note: Two pairs \((u_1, v_1)\) and \((u_2, v_2)\) are considered different if and only if \(u_1 \neq u_2\) or \(v_1 \neq v_2\).

inputFormat

The first line contains two integers \(n\) and \(m\) separated by a space, where \(n\) represents the number of students and \(m\) is the number of operations.

Each of the following \(m\) lines contains two integers \(l\) and \(r\) (with \(1 \le l \le r \le n\)), representing the interval for that operation.

outputFormat

For every operation, output a single line with one integer representing the number of student pairs in the interval \([l, r]\) that have not been acquainted before that operation.

sample

5 3
1 3
2 5
4 5

3
5
0