Problem Statement

There is an $N \times N$ grid. Initially, all cells are painted white.

Process $Q$ queries in the given order. Each query is one of the following:

• Type $1$: An integer $R$ is given. Paint all cells in the $R$-th row from the top of the grid black.
• Type $2$: An integer $C$ is given. Paint all cells in the $C$-th column from the left of the grid white.

After processing each query, output the number of black cells in the grid at that point.

Constraints

• $1 \leq N, Q \leq 3 \times 10^5$
• For type $1$ queries, $1 \leq R \leq N$.
• For type $2$ queries, $1 \leq C \leq N$.
• All input values are integers.

Input

The input is given from Standard Input in the following format:

N Q
\text{query}_1
\text{query}_2
\vdots
\text{query}_Q

Here, $\text{query}_i$ is the $i$-th query, given in one of the following formats.

Type $1$:

1 R

Type $2$:

2 C

Output

Output $Q$ lines. The $i$-th line should contain the number of black cells in the grid at the time the $i$-th query has been processed.