Cho một bảng kích thước \(N ∗ N\). Bạn cần thực hiện \(K\) truy vấn theo tuần tự, truy vấn thứ \(i\) chứa hai số nguyên dương \(x, y\). Với mỗi truy vấn thứ \(i\), bạn sẽ đánh dấu \('X'\) lên tất cả các ô nằm trên hàng \(x\) và tất cả các ô nằm trên cột \(y\).

Yêu cầu

Sau khi thực hiện xong từng truy vấn, in ra số lượng ô chưa bị tích dấu \('X'\) còn lại trên bảng.

Input

• Dòng đầu tiên chứa hai số nguyên dương \(N,K\) \((1 ≤ N ≤ 10^9, 1 ≤ K ≤ 1000)\)
• \(K\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(x, y\) \((1 ≤ x, y ≤ N)\)

Output

In ra \(K\) số trên một dòng là kết quả của từng truy vấn.

Example