题目描述

Bajtazar 正在练习，以成为一名 Forkbajt 的职业玩家。

Forkbajt 的游戏在一个 $n \times n$ 的棋盘上进行，其行和列用 $1$ 到 $n$ 的整数编号。在第 $1$ 行第 $1$ 列的格子上有着 Bajtazar 的城堡。在其余的每个格子上可能有一个障碍物或者一个堡垒。

整个游戏持续 $(q + 1)$ 天，而在这些天之间的每个夜晚，我们会收到关于建造或拆除某个堡垒的信息。

每一天，Bajtazar 必须向所有当前存在的堡垒发送消息。一天由许多回合组成。在每个回合中，Bajtazar 可以招募一名新英雄，并命令他从城堡前往其中一个堡垒（并在那里传递消息）。接下来，每位英雄可以移动到相邻的格子（左、右、上或下）。

英雄可以通过有堡垒的格子，但不能通过有障碍物的格子。也不能发生回合结束后两名英雄位于同一个格子上的情况。

我们感兴趣的是确定向所有堡垒传递消息所需的最小回合数。你的任务是为 $(q + 1)$ 天中的每一天确定向所有当前存在的堡垒传递消息所需的最小回合数。

我们保证没有任何堡垒会被与城堡“切断”，也就是说，从城堡到任何当前存在的堡垒都是可达的。

输入格式

输入的第一行包含两个整数 $n$ 和 $q$ ($2 \le n \le 1000$，$0 \le q \le 500000$)，表示棋盘的大小和天数。

接下来的 $n$ 行包含棋盘各行的描述。

一行的描述由 $n$ 个字符组成，描述该行中的连续格子，其中 # 表示障碍物，F 表示堡垒，. 表示空闲格子。

第 $1$ 行第 $1$ 列的格子将始终由 Z 描述，表示 Bajtazar 的城堡。 接下来的 $q$ 行包含棋盘上后续变化的描述。

在其中的第 $i$ 行（对于 $1 \le i \le q$）包含两个整数 $x_i, y_i$ ($1 \le x_i, y_i \le n$)，表示第 $x_i$ 行第 $y_i$ 列的格子（该格子上没有障碍物或 Bajtazar 的城堡）在第 $i$ 天和第 $i+1$ 天之间改变其状态：如果那里有一个堡垒，那么现在就没有了（被拆除），如果没有，那么现在就有了（被建造）。

输出格式

你的程序应该输出 $q + 1$ 行。

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

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

10
10
11
10

提示

样例解释

在第一个查询中，我们可以通过以下方式在 $10$ 个回合内向所有堡垒传递消息（第 $i$ 行代表第 $i$ 个英雄；列表示连续的回合）：

$$\begin{aligned} (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) \\ (1,2)\to &(1,3) \to (1,4) \to (2,4) \to (3,4) \to (4,4) \\ &(1,2) \to (1,3) \to (1,4) \to (2,4) \to (3,4) \end{aligned}$$

大样例

可以在附件中获得大样例。

样例 $\texttt{0a}$ 是题面中展示的样例。

此外：

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

子任务

本题采用捆绑测试。

子任务编号	限制	得分
$1$	$n \le 100, q \le 10^4$	$19$
$2$	$q=0$	$13$
$3$	$q \le 100000$，棋盘上没有障碍物	$17$
$4$	无额外限制	$51$