说明

经过一番艰苦的研究，Anton 决定去他的乡间别墅放松一下。他有一个美丽的花园，里面种着许多不同的花。但是，糟糕的是，他一到就发现地上有很多洞。是鼹鼠！

现在，Anton 将手持铁锹等待鼹鼠的出现。鼹鼠可能从任何一个洞里钻出来。Anton 想要选择一个位置，使得在最坏情况下，他跑到鼹鼠那里所需的时间最短。

花园可以表示为一个 $n \times m$ 的矩阵，其中 $n$ 是行数，$m$ 是列数。行从上到下编号为 $1$ 到 $n$。列从左到右编号为 $1$ 到 $m$。因此，索引为 $(1;1)$ 的单元格位于左上角。

花园的每个单元格 $a_{i, j}$ 描述了该单元格的状态：

• $a_{i, j}$ = $\tt{.}$ —— 该单元格没有花或洞；
• $a_{i, j}$ = $\tt{F}$ —— 该单元格有花；
• $a_{i, j}$ = $\tt{H}$ —— 该单元格有洞。

Anton 还知道洞的数量不超过 $100$。

作为一个在这些花上投入了大量时间的人，你不忍心践踏它们。因此，你需要找到一条不经过它们的路径。

在任何时刻，Anton 可以从位置 $(x, y)$ 移动到以下任意一个位置：$(x-1,y)$、$(x+1,y)$、$(x,y-1)$、$(x,y+1)$，前提是新位置不包含花且在花园范围内。

请找出所有位置 ($x,y$)，使得 Anton 在最坏情况下跑到鼹鼠那里所需的时间最短。

输入格式

• 第一行包含两个整数 $n$、$m$（$1 \le n \cdot m \le 2 \cdot 10^5$）——花园的长度和宽度。
• 接下来的 $n$ 行，每行包含 $m$ 个字符——花园的描述。

保证从每个不包含花的单元格出发，可以通过不经过花的单元格到达任何其他不包含花的单元格。

保证至少有一个洞，且花园中洞的数量不超过 $100$。

输出格式

• 第一行输出一个整数 $x$（$1 \leq x \leq n \cdot m$）——最优位置的数量。
• 接下来的 $x$ 行，每行输出一个等待鼹鼠的最优位置 ($x;y$)（$1 \le x \le n$，$1 \le y \le m$）。

位置可以按任意顺序输出。

3 4
HF.F
..HF
FF.F

2
2 1
2 2

4 9
......FFH
.F..FHFF.
HF.......
.FHF..FFF

2
1 6
3 4

提示

:::align{center} :::

设 $k$ 为花园中洞的数量。

• （$6$ 分）：$n = 1, m = 2$；
• （$9$ 分）：$n = 1$；
• （$15$ 分）：$k = 1, n \cdot m \le 5 \cdot 10^3$；
• （$22$ 分）：$n \cdot m \le 5 \cdot 10^3$；
• （$17$ 分）：$k = 1$；
• （$31$ 分）：无额外限制。

翻译由 DeepSeek V3 完成