djb 的多米诺

题目描述

djb 在一个 $n * n$ 的矩形网格的正中间放了共计 $(n - 2) * (n - 2)$ 个正方形多米诺骨牌 如下形状（用 $1$ 表示多米诺骨牌，$0$ 表示为空)：

000000 011110 011110 011110 011110 000000

接下来 djb 会进行 $Q$ 次操作，操作分为两种：

从左往右推倒 $(i,2)$ 的多米诺骨牌

从上往下推倒 $(2,i)$ 的多米诺骨牌

众所周知，多米诺骨牌在被推倒时，会连带把倒向的多米诺骨牌一起推倒，直到该方向下一格没有多米诺骨牌为止

例如如上的网格， djb 从上往下推倒 $(2,4)$ 的多米诺骨牌后变为

000000 011010 011010 011010 011010 000000

接着 djb 从左往右推倒 $(4,2)$ 的多米诺骨牌：

000000 011010 011010 000010 011010 000000

现在 djb 想知道，$T$ 次操作以后，网格上还有多少多米诺骨牌还没倒？

输入格式

第一行输入两个正整数 $n,T$， 表示网格大小和操作次数

接下来 $T$ 行，每行包含两个整数 $op, x$ 若 $op == 1$ 表示 djb 从上往下推倒了 $(2,x)$ 这块多米诺骨牌 若 $op == 2$ 表示 djb 从左往右推倒了 $(x,2)$ 这块多米诺骨牌

输出格式

输出一个整数，表示还没倒的多米诺骨牌数量

数据范围

对于 $30\%$ 的数据：$n \leq 2000$。

对于 $70\%$ 的数据：时限$1$s。

对于最后 $30\%$ 的数据：时限 $500ms$。

对于 $100\%$ 的数据：$n \leq 2\times 10^5,1\leq T \leq \min(2n-4,2\times 10^5),2\leq x\leq n-1$

特别的保证： djb 不会推倒同一块多米诺骨牌

样例输入

6 2
1 4
2 4

样例输出

10