AT_abc461_e.E-liter

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.

有一个 $N \times N$ 的网格。初始时，所有格子均为白色。

按给定顺序处理 $Q$ 个查询。每个查询为以下两种类型之一：

• 类型 $1$：给出一个整数 $R$，将网格中从上往下数第 $R$ 行的所有格子涂成黑色。
• 类型 $2$：给出一个整数 $C$，将网格中从左往右数第 $C$ 列的所有格子涂成白色。

在每次查询处理完毕后，输出此时网格中黑色格子的数量。

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$

输入从标准输入中以如下格式给出：

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

其中，$\text{query}_i$ 表示第 $i$ 个查询，其格式为以下两种之一。

类型 $1$：

1 $R$

类型 $2$：

2 $C$

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.

输出 $Q$ 行。第 $i$ 行应包含处理完第 $i$ 个查询时网格中黑色格子的数量。

Sample 1 Explanation:
The changes in the grid are shown using characters. . represents a white cell, and # represents a black cell.

Sample 2 Explanation:
Beware of overflow in larger cases.

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.

样例 1 解释：
网格的变化使用字符表示。. 表示白色格子，# 表示黑色格子。

样例 2 解释：
注意在较大规模情况下可能出现整数溢出。

限制条件

• $1 \leq N, Q \leq 3 \times 10^5$
• 对于类型 $1$ 的查询，满足 $1 \leq R \leq N$。
• 对于类型 $2$ 的查询，满足 $1 \leq C \leq N$。
• 所有输入值均为整数。