No testdata at current.

棋盘

时空限制

• CPU占用时长: 1秒
• 内存使用限制: 128MB

题目描述

小Y有一个 $n \times n$ 棋盘，开始时这个棋盘每个格子的颜色是白黑相间的，即第一行的第 $1,3,5\ldots$ 个格子是白色，第 $2,4,6\ldots$ 个格子是黑色，第二行第 $2,4,6\ldots$ 个格子是白色，第 $1,3,5\ldots$ 个格子是黑色，如标准国际象棋棋盘所示。

小 $Y$ 会进行 $q$ 次操作，每次操作会将某一行或者某一列的所有格子的颜色反转，即白色格子变成黑色格子，黑色格子变成白色格子。

小 $Y$ 想知道，在每次操作之后，一共有多少个同颜色（全黑或全白）的联通区域。这里联通指的是四联通，即两个格子之间有边相邻才算联通。

输入格式

第一行2个正整数 $n, q$，表示棋盘的大小和操作的次数。

第2到 $q+1$ 行每行2个正整数 $opt[i], a[i]$，若 $opt[i]$ 为1则表示反转的是行，为2则表示反转的是列，$a[i]$ 表示反转的是第几行/列。

输出格式

输出 $q$ 行每行一个整数，表示在经过该次操作后，一共有多少个同颜色的联通区域。

输入输出样例

样例 1

输入：

3 3
1 2
2 3
1 2

输出：

3
2
6

说明： 初始棋盘白黑相间，第一次操作后有3个同颜色的联通区域，第二次操作后有2个同颜色的联通区域，第三次操作后有6个同颜色的联通区域。

样例 2

输入：

100000 1
1 1

输出：

9999900000

样例 3

输入：

15000 5
1 90
1 1231
1 91
1 1233
1 1232

输出：

224970000
224940000
224940000
224910000
224940000

数据范围与提示

本题共有 10 个测试点，每个测试点 12 分。

对于全部测试点：$1 \le q, n \le 10^5$，$1 \le opt[i] \le 2$，$1 \le a[i] \le n$

• 对于测试点 1-4：$1 \le n \le 4$，$1 \le q \le 10$
• 对于测试点 5-6：$1 \le n \le 10^5$，$q = 1$
• 对于测试点 7-9：$1 \le n \le 10^5$，保证同一个测试点所有的 $opt[i]$ 均相等