Counting Intact Rectangles in a Crumbling Dungeon

Professor Pang is trapped in a dungeon! The dungeon room is represented by an $n \times m$ chessboard where the cell at row $i$ and column $j$ is denoted by $(i,j)$ for $1\le i\le n$ and $1\le j\le m$. Every second, the floor of one cell breaks (making it impossible for Professor Pang to stand there). After $nm$ seconds, all the cells have broken and there is nowhere to stand.

Remaining calm, Professor Pang calculates the number of subrectangles (defined by four integers $a, b, c, d$ with $1\le a\le b\le n$ and $1\le c\le d\le m$) such that every cell in the rectangle is intact at that moment. Initially, all cells are intact so the number of subrectangles is $\frac{n(n+1)}{2}\times\frac{m(m+1)}{2}$. As the cells break one by one according to a given order, you are to compute and output the number of intact subrectangles after each break.

inputFormat

The first line contains two integers $n$ and $m$, the dimensions of the dungeon room.

The next $nm$ lines each contain two integers $i$ and $j$, indicating that the cell $(i,j)$ breaks at that second. The order of these lines is the order in which the cells break.

outputFormat

Output $nm$ lines. The $k$-th line should contain a single integer representing the number of subrectangles that remain entirely intact (with no broken cell) after the first $k$ seconds.

sample

2 2
1 1
1 2
2 1
2 2

9
4
1
0