题目描述

有一个由 $N$ 行和 $N$ 列方格组成的网格。$(i,j)$ 表示位于从上往下数第 $i$ 行、从左往右数第 $j$ 列的方格。

网格中间的 $(N-2) \\times (N-2)$ 个方格上都有黑色石头。底边和右边共有 $2N - 1$ 个方格上放着白色石头。

给出 $Q$ 个查询。请你按顺序处理它们。查询有两种类型，其输入格式和描述如下：

• 1 x：在 $(1, x)$ 放置一个白色石头。之后，对于从 $(1, x)$ 向下走，直到遇到第一个白色石头之前的每个黑色石头，都将其替换为白色石头。
• 2 x：在 $(x, 1)$ 放置一个白色石头。之后，对于从 $(x, 1)$ 向右走，直到遇到第一个白色石头之前的每个黑色石头，都将其替换为白色石头。

在处理完所有的 $Q$ 个查询后，网格上还有多少个黑色石头？

约束条件

• $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$
• 这些查询两两不相同。

输入

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

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

输出

输出处理完所有 $Q$ 个查询后，网格上还有多少个黑色石头。

示例输入 1

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

示例输出 1

1

每次查询后，网格变化如下：

示例输入 2

200000 0

示例输出 2

39999200004

示例输入 3

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

示例输出 3

31159505795