Đặt quân xe lên bàn cờ

Cho bàn cờ \(n \times n\) ban đầu trống. Ta lần lượt đặt \(m\) quân xe. Một ô bị tấn công nếu cùng hàng hoặc cùng cột với ít nhất một quân xe (ô chứa xe cũng bị tấn công). Đặt xe vào ô đã có xe thì không thay đổi gì.

Sau mỗi lần đặt, cho biết có bao nhiêu ô không bị tấn công.

Input

• Dòng đầu: \(n\) và \(m\).
• \(m\) dòng: \(x_i, y_i\) là hàng và cột của quân xe thứ \(i\).

Output

In \(m\) số trên một dòng, cách nhau bởi dấu cách; số thứ \(i\) là số ô không bị tấn công sau \(i\) quân đầu.

Constraints

• \(1 \le n \le 10^5\)
• \(1 \le m \le \min(10^5, n^2)\)
• \(1 \le x_i, y_i \le n\)

Sample Input

4 3
2 3
2 1
4 4

Sample Output

9 6 2

Explanation

Sau quân đầu: hàng \(\{2\}\), cột \(\{3\}\) nên còn \(3 \cdot 3 = 9\) ô. Sau quân hai: cột \(\{3,1\}\) còn \(3 \cdot 2 = 6\). Sau quân ba: hàng \(\{2,4\}\), cột \(\{1,3,4\}\) còn \(2 \cdot 1 = 2\).