题目描述

Farmer John 有一块正方形画布，由一个 $N$ 行 $N$ 列的方阵表示（$2 \leq N \leq 2000$，$N$ 为偶数）。他按照以下步骤来绘制画布：

首先，他将画布分成四个等大的象限，由通过画布中心的水平和垂直直线分隔。 其次，他在画布的右上象限中绘制了一幅美丽的画作。右上象限的每个方格或者被涂色（以 # 表示），或者未被涂色（以 . 表示）。 最后，由于他对自己的画作感到非常自豪，他将其沿此前提到的水平和垂直直线翻转到画布的其他象限中。 例如，假设 $N=8$，且 FJ 在步骤 2 中于右上象限绘制了以下画作：

.#..
.#..
.##.
....

在步骤 3 中沿水平和垂直直线翻转过后，画布将如下所示：

..#..#..
..#..#..
.##..##.
........
........
.##..##.
..#..#..
..#..#..

然而，当 FJ 熟睡时，Bessie 闯入了他的牛棚，偷走了他珍贵的画布。她彻底破坏了画布——移除了某些涂色的单元格，同时添加了某些涂色的单元格！在 FJ 醒来之前，她将画布归还给了 FJ。

FJ 想要修改他的画布，使其再次满足翻转条件：即，它是将右上象限翻转到其他各象限的结果。由于他只有有限的资源，他希望以尽可能少的操作来实现这一点，其中单次操作包括为一个方格涂色或移除一个方格的涂色。

给定 Bessie 破坏后的画布，以及一系列 $U$（$0\le U \leq 10^5$）次对画布的更新，每次更新切换单个方格的状态，若它是 '#' 则切换为 '.'，反之亦然。在所有更新之前，以及在每次更新之后，输出 FJ 为满足翻转条件所需要执行的最小操作数量 $x$。

输入格式

输入的第一行包含整数 $N$ 和 $U$。

以下 $N$ 行，每行包含 $N$ 个字符，表示 Bessie 破坏后的画布。每个字符均为 # 或 .。

以下 $U$ 行，每行包含整数 $r$ 和 $c$，其中 $1 \leq r, c \leq N$，表示一次对画布从上到下第 $r$ 行，从左到右第 $c$ 列的方格的更新。

输出格式

输出 $U+1$ 行，为在所有更新之前以及在每次更新之后的 $x$。

4 5
..#.
##.#
####
..##
1 3
2 3
4 3
4 4
4 4

4
3
2
1
0
1

提示

样例 1 解释：

以下画布满足翻转条件，并且可由原画布经过 4 次操作得到：

....
####
####
....

使用少于 4 次操作使原画布满足翻转条件是不可能的。

在更新 $(1, 3)$ 之后，画布看起来是这样的：

....
##.#
####
..##

现在需要 3 次操作使画布满足翻转条件。

在更新 $(2, 3)$ 之后，画布看起来是这样的：

....
####
####
..##

现在需要 2 次操作使画布满足翻转条件。

• 测试点 $2\sim 3$：$N \le 4$。
• 测试点 $4\sim 6$：$U \le 10$。
• 测试点 $7\sim 16$：没有额外限制。