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
注意
下图显示了放置三辆车后棋盘的状态。涂成灰色的细胞没有受到攻击。