Prof. Pang 进入了地下城中的一个陷阱房间。这个房间可以表示为一个 $n \times m$ 的棋盘。我们用 $(i, j)$ ($1 \le i \le n, 1 \le j \le m$) 来表示第 $i$ 行第 $j$ 列的格子。每一秒钟，有一个格子的地板会破碎（这意味着 Prof. Pang 不能再站在那个格子上）。$nm$ 秒后，将没有任何格子可以站立，Prof. Pang 将会掉落到下一层（更深、更危险）。

但 Prof. Pang 知道冷静是克服任何挑战的关键。因此，他没有惊慌，而是计算了每一秒钟后，所有格子都完好无损（即没有破碎）的矩形的数量。（一个由四个整数 $a, b, c, d$ ($1 \le a \le b \le n, 1 \le c \le d \le m$) 表示的矩形包含所有满足 $a \le i \le b, c \le j \le d$ 的格子 $(i, j)$。总共有 $\frac{n(n+1)}{2} \times \frac{m(m+1)}{2}$ 个矩形。）

输入格式

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

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

输出格式

输出 $nm$ 行。第 $i$ 行应包含在前 $i$ 个格子破碎后，所有格子都完好无损的矩形数量。

样例

输入 1

2 2
1 1
2 1
1 2
2 2

输出 1

5
3
1
0

说明

在样例中，第一秒后，有 3 个面积为 1 的矩形和 2 个面积为 2 的矩形满足条件。因此第一行应包含 5。第二秒后，只有第二列的格子保持完好。答案应为 3。第三秒后，只有一个格子保持完好。答案应为 1。第四秒后，所有格子都破碎了，因此答案应为 0。