题目描述

有一个 $N \times N$ 的网格。初始时，所有的单元格都被涂成白色。

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

• 类型 1：给出一个整数 $R$。将网格中第 $R$ 行的所有单元格涂成黑色；
• 类型 2：给出一个整数 $C$。将网格中第 $C$ 列的所有单元格涂成白色。

在处理完每一个查询后，输出当前网格中黑色单元格的总数。

输入格式

N Q
query_1
query_2
...
query_Q

每个查询按以下格式之一给出：

• 类型 1: 1 R
• 类型 2: 2 C

输出格式

输出 $Q$ 行。第 $i$ 行表示第 $i$ 个查询处理完成后，当前网格中黑色单元格的数量。

输入示例 1

3 4
1 1
1 3
2 2
1 1

输出示例 1

3
6
4
5

示例 1 说明

用 . 表示白色单元格，# 表示黑色单元格。网格变化过程：

...      ###      ###      #.#      ###
...  →   ...  →   ...  →   ...  →   ...
...      ...      ###      #.#      #.#

• 操作 $1$（第 $1$ 行变全黑）后：黑格数 $3$；
• 操作 $2$（第 $3$ 行变全黑）后：黑格数 $6$；
• 操作 $3$（第 $2$ 列变全白）后：黑格数 $4$；
• 操作 $4$（第 $1$ 行变全黑）后：黑格数 $5$（第 $1$ 行恢复 $3$ 个黑格，第 $3$ 行仍保留 $2$ 个黑格）。

输入示例 2

5 8
1 3
2 4
1 2
1 5
2 3
1 1
2 1
1 4

输出示例 2

5
4
9
14
11
16
12
17

示例 2 说明

请注意更大数据下可能出现的溢出问题（答案可能超过 int 范围）。

约束条件

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