拜塔扎尔正在训练，以成为一名职业的 Forkbajt 玩家。Forkbajt 的游戏在一个 $n \times n$ 的网格上进行，其行和列从 $1$ 到 $n$ 编号。位于第 $1$ 行第 $1$ 列的格子是拜塔扎尔的城堡。其余的每个格子上可能有一个障碍物，或者一个堡垒。整个游戏持续 $q + 1$ 天，在每两天的夜里，我们会收到关于建造或拆除某个堡垒的信息。

每天，拜塔扎尔必须向所有当前存在的堡垒发送消息。一天由多个回合组成。在每个回合中，拜塔扎尔可以招募一名新的英雄，并命令他从城堡出发前往其中一个堡垒（并在那里传递消息）。接着，每位英雄可以移动到相邻的格子（向左、向右、向上或向下）。英雄可以经过有堡垒的格子，但不能经过有障碍物的格子。在任何一个回合结束时，不能有两名英雄位于同一个格子上。我们希望确定向所有堡垒传递消息所需的最少回合数。

你的任务是，对于这 $q + 1$ 天中的每一天，求出向所有当前存在的堡垒传递消息所需的最少回合数。我们保证没有任何堡垒会与城堡“断开连接”，也就是说，总是可以从城堡到达任何当前存在的堡垒。

输入格式

输入的第一行包含两个整数 $n$ 和 $q$（$2 \le n \le 1000$，$0 \le q \le 500\,000$），分别表示网格的大小和天数。

接下来的 $n$ 行包含对网格各行的描述。一行的描述由 $n$ 个字符组成，其中：

• # 表示障碍物，
• F 表示堡垒，
• . 表示空地。

第 $1$ 行第 $1$ 列的格子总是由 Z 表示，代表拜塔扎尔的城堡。

接下来的 $q$ 行包含对网格后续变化的描述。其中第 $i$ 行（对于 $1 \le i \le q$）包含两个整数 $x_i, y_i$（$1 \le x_i, y_i \le n$），表示在第 $i$ 天和第 $i+1$ 天之间，位于第 $x_i$ 行第 $y_i$ 列的格子（该格子既没有障碍物也不是拜塔扎尔的城堡）改变了状态：如果之前是堡垒，则现在不再是（被拆除）；如果之前不是，则现在是（被建造）。

输出格式

你的程序应该输出 $q + 1$ 行。在第 $i$ 行（对于 $1 \le i \le q + 1$）中，输出在第 $i$ 天向所有堡垒传递消息所需的最少回合数。

样例

输入样例 1

4 3
Z...
###.
F.#F
...F
3 2
4 1
3 1

输出样例 1

10
10
11
10

说明

样例解释：在第一天（第 1 次询问），我们可以在 10 个回合内将消息传递到所有堡垒，具体方式如下（各列表示连续的回合）：

• 英雄 1：$(1, 2) \to (1, 3) \to (1, 4) \to (2, 4) \to (3, 4) \to (4, 4) \to (4, 3) \to (4, 2) \to (3, 2) \to (3, 1)$
• 英雄 2：$(1, 2) \to (1, 3) \to (1, 4) \to (2, 4) \to (3, 4) \to (4, 4)$
• 英雄 3：$(1, 2) \to (1, 3) \to (1, 4) \to (2, 4) \to (3, 4)$

其他样例测试：测试 0a 为上述样例。此外：

• 0b：$n = 6, q = 0$，除了 $(1, 1)$（城堡）和 $(6, 6)$（障碍物）外，所有格子上都有堡垒。
• 0c：$n = 1000, q = 100\,000$，网格上没有障碍物，堡垒从最远可能的位置开始依次出现，然后以相同的顺序依次消失。

子任务

测试集分为以下子任务。每个子任务的测试由一个或多个独立的测试点组组成。