← 返回题目列表

Codeforces · 701/B

B. 细胞未受到攻击

中文机器翻译题面 查看原题

Vasya 有一个大小为 n × n 和 m 车的方形棋盘。最初棋盘是空的。 Vasya 会将这些车依次放在棋盘上。

如果至少有一个车与该方格位于同一行或同一列,则该方格受到车的攻击。如果牢房内有车,则该牢房也会受到攻击。

您将获得 Vasya 将放置车的棋盘位置。对于每个车,您必须确定 Vasya 将其放在棋盘上后未受到攻击的单元格数量。

输入

输入的第一行包含两个整数 n 和 m (1 ≤ n ≤ 100 000, 1 ≤ m ≤ min(100 000, n2)) - 棋盘的大小和车的数量。

接下来的 m 行中的每一行都包含整数 xi 和 yi (1 ≤ xi, yi ≤ n) - Vasya 将放置第 i 个车的行号和列号。 Vasya 按照车在输入中出现的顺序将车放在棋盘上。保证任何单元格中不会包含超过一只车。

输出

打印m个整数,其中第i个应该等于放置前i个车后未受到攻击的单元格数量。

示例

输入 #1

3 3
1 1
3 1
2 2

输出 #1

4 2 0

输入 #2

5 2
1 5
5 1

输出 #2

16 9

输入 #3

100000 1
300 400

输出 #3

9999800001

注意

下图显示了放置三辆车后棋盘的状态。涂成灰色的细胞没有受到攻击。