题目背景

落子无悔，纵横棋局。

问题描述

\(n\times n\) 的棋盘， 依次给出 \(m\) 对坐标， 表示一个棋子的坐标，放了棋子的点的行和列都被占有，依次询问放 \(i\) 个棋子后还有多少位置没有被占。

输入格式

输入的第一行包含 \(2\) 个整数 \(n, m\) 分别表示棋盘大小和棋子个数。
然后有 \(n\) 行， 每行包含 \(2\) 个数 \(x,y\)（\(1\le x,y\le n\) ） ，代表第 \(i-1\) 个棋子放的位置。

输出格式

输出 \(m\) 个数，每个数之间用空格隔开，代表放了前 \(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

数据范围

测试点编号	数据限制
\(1-4\)	\(n,m\le 1000\)
\(5-6\)	\(n\le 100000;0\le m\le 10\)
\(7-10\)	\(n\le 10^9;m\le 100000\)

时空限制

\(1\mathrm s,512\mathrm{MiB}\)