题目描述

Prof. Pang enters a trap room in a dungeon. The room can be represented by an $n$ by $m$ chessboard. We use $(i, j)$ ($1\le i\le n$, $1\le j\le m$) to denote the cell at the $i$-th row and $j$-th column. Every second, the floor of one cell breaks apart (so that Prof. Pang can no longer stand on that cell.) After $nm$ seconds, there will be no cell to stand on and Prof. Pang will fall through to the next (deeper and more dangerous) level.

But Prof. Pang knows that calm is the key to overcome any challenge. So instead of being panic, he calculates the number of rectangles such that every cell in it is intact (i.e., not broken) after every second. (A rectangle represented by four integers $a, b, c$ and $d$ ($1\le a\le b\le n, 1\le c\le d\le m$) includes all cells $(i, j)$ such that $a\le i\le b, c\le j\le d$. There are $\frac{n(n+1)}{2} \times \frac{m(m+1)}{2}$ rectangles in total.)

输入格式

The first line contains two integers $n$, $m$ ($1\le n, m\le 500$) separated by a single space.

The $(i+1)$-th line contains two integers $a$, $b$ separated by a single space representing that the cell $(a, b)$ breaks apart at the $i$-th second. It is guaranteed that each cell appears exactly once in the input.

输出格式

Output $nm$ lines. The $i$-th line should contain the number of rectangles such that every cell in it is intact after the first $i$ cells break apart.

题目大意

题目描述

庞教授进入了一个地下城的陷阱房间。这个房间可以用一个 $n$ 行 $m$ 列的棋盘来表示。我们用 $(i, j)$ ($1\le i\le n$, $1\le j\le m$) 来表示第 $i$ 行第 $j$ 列的单元格。每秒钟，有一个单元格的地板会破裂（这样庞教授就不能再站在这个单元格上了）。经过 $nm$ 秒后，将没有单元格可供站立，庞教授将跌落到下一个（更深且更危险的）层级。

但庞教授知道冷静是克服任何挑战的关键。因此，他没有惊慌，而是计算了在每秒钟后，所有单元格都完好的矩形的数量（即，每个单元格在矩形中都没有破裂）。一个矩形由四个整数 $a, b, c$ 和 $d$ ($1\le a\le b\le n, 1\le c\le d\le m$) 表示，包含所有 $(i, j)$ 使得 $a\le i\le b, c\le j\le d$。总共有 $\frac{n(n+1)}{2} \times \frac{m(m+1)}{2}$ 个矩形。

输入格式

第一行包含两个整数 $n$, $m$ ($1\le n, m\le 500$)，用空格分隔。

第 $(i+1)$ 行包含两个整数 $a$, $b$，表示在第 $i$ 秒钟单元格 $(a, b)$ 破裂。保证每个单元格在输入中出现恰好一次。

输出格式

输出 $nm$ 行。第 $i$ 行应包含在前 $i$ 个单元格破裂之后，每个单元格都完好的矩形的数量。

提示

在示例中：在第一秒后，有 $3$ 个面积为 $1$ 的矩形和 $2$ 个面积为 $2$ 的矩形满足条件。因此第一行应该输出 $5$。在第二秒后，仅第二列中的单元格保持完好。答案应该是 $3$。在第三秒后，仅一个单元格保持完好。答案应该是 $1$。在第四秒后，所有单元格都破裂，所以答案应该是 $0$。

翻译者：Immunoglobules

2 2
1 1
2 1
1 2
2 2

5
3
1
0

提示

In the example, after the first second, there are $3$ rectangles of area $1$ and $2$ rectangles of area $2$ that satisfy the constraint. So the first line should contain a $5$. After the second second, only cells in the second column remains intact. The answer should be $3$. After the third second, only one cell remains intact. The answer should be $1$. After the fourth second, all cells broke apart so the answer should be $0$.