Cells in a matrix
Tag(s):

## 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
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, C++17, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, Java 14, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, Python 3.8, R(RScript), Racket, Ruby, Rust, Scala, Swift-4.1, Swift, TypeScript, Visual Basic

## CODE EDITOR

Initializing Code Editor...

## This Problem was Asked in

Challenge Name

Team_challenges for demo

OTHER PROBLEMS OF THIS CHALLENGE
• Algorithms > Dynamic Programming