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$