Các ô trong ma trận

Trong một buổi tình nguyện tại trường học, FullHouse Dev được giao nhiệm vụ giúp các em học sinh hiểu về ma trận và cách xử lý dữ liệu. Họ đã thiết kế một bài toán thú vị về việc đánh dấu các ô trong ma trận để giúp học sinh rèn luyện tư duy logic.

Bài toán

FullHouse Dev được cho một ma trận \(N \times N\). Ban đầu, tất cả các ô trong ma trận đều trống. Họ phải thực hiện \(Q\) nhiệm vụ. Trong mỗi nhiệm vụ, họ được cho một ô \((r,c)\) trong đó \(r\) là hàng và \(c\) là cột của ma trận.

Mỗi nhiệm vụ phải được thực hiện tuần tự theo thứ tự cho trước. Với mỗi nhiệm vụ tại ô \((r,c)\), họ phải đánh dấu tất cả các ô trên hàng \(r\) và cột \(c\). Sau khi hoàn thành mỗi nhiệm vụ, họ cần đếm số ô còn trống trong ma trận.

INPUT FORMAT:

• Dòng đầu tiên chứa hai số nguyên \(N\) và \(Q\), trong đó \(N\) là số hàng và cột của ma trận, \(Q\) là số lượng nhiệm vụ.
• \(Q\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(r\) và \(c\).

OUTPUT FORMAT:

• In ra \(Q\) số nguyên cách nhau bởi dấu cách, mỗi số biểu thị số lượng ô trống trong ma trận sau khi hoàn thành mỗi nhiệm vụ.

Ràng buộc:

• \(1 \leq N \leq 100000\)
• \(1 \leq Q \leq 10000\)
• \(1 \leq r,c \leq N\)

Ví dụ

INPUT

3 3
1 1
1 3
3 2

OUTPUT

4 2 0

Giải thích

Ban đầu tất cả các ô [{1,1}, {1,2}, {1,3}, {2,1}, {2,2}, {2,3}, {3,1}, {3,2}, {3,3}] đều trống.

Sau nhiệm vụ đầu tiên: Các ô trống còn lại là [{2,2}, {2,3}, {3,2}, {3,3}]. Do đó, đáp án là 4.

Sau nhiệm vụ thứ hai: Các ô trống còn lại là [{2,2}, {3,2}]. Do đó, đáp án là 2.

Sau nhiệm vụ thứ ba: Không còn ô trống nào. Do đó, đáp án là 0.