简化

题目描述

有一个纵 $N$ 格、横 $N$ 格的网格。将从上数第 $i$ 行、从左数第 $j$ 列的格子记为格子 $(i,j)$。

在网格中央的 $(N-2)\times (N-2)$ 个格子中各放有 $1$ 个黑石,在下边和右边共 $2N-1$ 个格子中各放有 $1$ 个白石。

给定 $Q$ 个查询,请按顺序处理。查询有两种类型,输入格式和内容如下:

• 1 x:在 $(1,x)$ 放置白石。将从该处向下数直到遇到最近的白色石头为止之间的所有黑石替换为白石。
• 2 x:在 $(x,1)$ 放置白石。将从该处向右数直到遇到最近的白色石头为止之间的所有黑石替换为白石。

处理完所有 $Q$ 个查询后,网格上还剩多少个黑石?

输入格式

输入按以下格式从标准输入给出:

$N$ $Q$
$Query_1$
$\vdots$
$Query_Q$

输出格式

输出处理完所有 $Q$ 个查询后网格上黑石的个数。

样例

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

1

网格随每个查询的变化如下。

200000 0

39999200004

176527 15
1 81279
2 22308
2 133061
1 80744
2 44603
1 170938
2 139754
2 15220
1 172794
1 159290
2 156968
1 56426
2 77429
1 97459
2 71282

31159505795

数据范围

• $3 \leq N \leq 2\times 10^5$
• $0 \leq Q \leq \min(2N-4,2\times 10^5)$
• $2 \leq x \leq N-1$
• 不会给出相同的查询多次