小Y 有一个n*n 棋盘，开始时这个棋盘每个格子的颜色是白黑相间的，即第一行的第1,3,5……个格子是白色，第2,4,6……个格子是黑色，第二行第2,4,6……个格子是白色，第1,3,5……个格子是黑色，如下图所示。

小Y 会进行q 次操作，每次操作会将某一行或者某一列的所有格子的颜色反转，即白色格子变成黑色格子，黑色格子变成白色格子。小Y 想知道，在每次操作之后，一共有多少个同颜色(全黑或全白)的联通区域。这里联通指的是四联通，即两个格子之间有边相邻才算联通。

第1行2 个正整数n，q，表示棋盘的大小和操作的次数。
第2 到q+1 行每行2 个正整数opt[i]，a[i]，若opt[i]为1 则表示反转的是行，为2 则表示反转的是列，a[i]表示反转的是第几行/列。

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

样例二：
输入：
100000 1
1 1
输出：
9999900000


样例三：
输入：
15000 5
1 90
1 1231
1 91
1 1233
1 1232
输出：
224970000
224940000
224940000
224910000
224940000

样例一解释：

初始棋盘白黑相间，第一次操作后有3 个同颜色的联通区域，第二次操作后有2 个同颜色的联通区域，第三次操作后有6 个同颜色的联通区域。
【数据范围】
本题共有10 个测试点，每个测试点12 分
对于全部测试点：1≤q, n≤10^5, 1≤opt[i]≤2, 1≤a[i]≤n
对于测试点1-4：1≤n≤4, 1≤q≤10
对于测试点5-6：1≤n≤10^5, q=1
对于测试点7-9：1≤n≤10^5, 保证同一个测试点所有的opt[i]均相等

信息未来