题目描述

縦 $N$ マス、横 $N$ マスのグリッドがあります。上から $i$ 行目、左から $j$ 列目のマスをマス$(i,j)$ と表します。

グリッドの中央 $(N-2)\times\ (N-2)$ マスには黒い石が $1$ 個ずつ置いてあり、下辺と右辺の計 $2N-1$ マスには白い石が $1$ 個ずつ置いてあります。

$Q$ 個のクエリが与えられるので、順番に処理してください。 クエリには $2$ 種類あり、入力形式とクエリの内容は以下のとおりです。

• 1 x： $(1,x)$ に白い石を置く。そこから下方向に最も近い白い石との間にある黒い石を全て白い石に置き換える
• 2 x： $(x,1)$ に白い石を置く。そこから右方向に最も近い白い石との間にある黒い石を全て白い石に置き換える

$Q$ 個のクエリを全て処理したあとグリッド上に黒い石はいくつありますか。

输入格式

入力は以下の形式で標準入力から与えられる。

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

输出格式

$Q$ 個のクエリを全て処理したあとグリッド上にある黒い石の個数を出力せよ。

题目大意

有一个边长为 $N$ 正方形的网格，$(i,j)$ 为第 $i$ 行第 $j$ 列的正方形。

网格中央 $(N − 2)\times(N − 2)$ 的每个方格上都有一个黑色的石头。底部和右侧的方格中，每个方格上都有一块白色的石头。

给出了 $Q$ 个查询，有两种查询。它们的输入格式和描述如下:

• 在 $(1,x)$ 上放一个白色石头。之后，对于 $(1,x)$ 和 $(1,x)$ 之间的每一个黑色石头，如果你从 $(1,x)$ 开始，用白色石头替换它。
• 在 $(x,1)$ 上放一个白色石头。之后，对于 $(x,1)$ 和 $(x,1)$ 之间的每一个黑色石头，如果你从 $(x,1)$ 开始，你击中的第一个白色石头，用白色石头替换它。

在处理完所有 $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$
• 同じクエリが複数回与えられることはない

Sample Explanation 1

各クエリにより、グリッドは次のように変化します。