Cells in a matrix
/

## Algorithms, Data Structures, Hash Tables, Math

Problem
Editorial
Analytics

You are given an integer $N$ denoting an $N \times N$ matrix. Initially, each cell of the matrix is empty. You are given $K$ tasks. In each task, you are given a cell $(i,j)$ where cell $(i,j)$ represents the $i^{th}$ row and $j^{th}$ column of the given matrix.

You have to perform each task sequentially in the given order. Each task is described in cell $(i,j)$. For each task, you have to place $X$ in each cell of row $i$ and each cell column $j$. After you complete each task, you are required to print the number of empty cells in the matrix.

Input format

• The first line contains two space-separated integers $N$ and $K$ where $N$ is the number of rows and columns in the given matrix and $K$ is the number of tasks respectively.
• Next $K$ lines contain two space-separated integers $i$ and $j$.

Output format

Print $K$ space-separated integers denoting the number of empty cells in the matrix.

Constraints

$1 \le N \le 10^5$

$1 \le K \le 1000$

$1 \le i , j \le N$

SAMPLE INPUT
3 3
1 1
1 3
3 2

SAMPLE OUTPUT
4 2 0

Explanation

Initally all the cells [{1, 1}, {1, 2}, {1, 3}, {2, 1}, {2, 2}, {2, 3}, {3, 1}, {3, 2}, {3, 3}] are empty.

Empty cells are [{2, 2}, {2, 3}, {3, 2}, {3, 3}]. Therefore, the answer is 4.

Empty cells are [{2, 2}, {3, 2}]. Therefore, the answer is 2.

No cells remain empty. Therefore, the answer is 0.

Time Limit: 5.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB

## This Problem was Asked in

Initializing Code Editor...