题目描述

After a difficult research, Anton decided to relax at his country house. He has a beautiful garden with many different flowers. But, oh no, upon arrival he saw a significant number of holes in the ground. It's a mole!

Now, armed with a shovel, Anton will be waiting for the mole. The mole can emerge from any hole. Anton wants to choose a position so that in the worst case, he runs to the mole in the $\textbf{minimum}$ amount of time.

The garden can be represented as a matrix $n \times m$, where $n$ is the number of rows, and $m$ is the number of columns. Rows are numbered from top to bottom, from $1$ to $n$. Columns are numbered from left to right, from $1$ to $m$. Thus, the cell with index $(1;1)$ is located in the upper left corner.

Each cell of the garden $a_{i, j}$ describes the state of this cell:

• $a_{i, j}$ = $\tt{.}$ --- this cell does not contain flowers or holes;
• $a_{i, j}$ = $\tt{F}$ --- this cell contains flowers;
• $a_{i, j}$ = $\tt{H}$ --- this cell contains a hole.

Anton also knows that the number of holes does not exceed $100$.

As a person who has put a lot of time into these flowers, your heart cannot bear trampling on them. Therefore, you need to find a path in such a way that it does not pass through them.

At any moment in time, Anton can move from position $(x, y)$ to any of the following positions: $(x-1,y)$, $(x+1,y)$, $(x,y-1)$, $(x,y+1)$, provided that the new position does not contain flowers and is inside the garden.

Find all positions ($x;y$) from which Anton will run to the moles in the worst case in the minimum amount of time.

输入格式

The first line contains two integers $n$, $m$ ($1 \le n \cdot m \le 2 \cdot 10^5$) --- the length and width of the garden.

The next $n$ lines contain $m$ characters each --- the description of the garden.

It is guaranteed that from each cell that does not contain flowers, it is possible to reach any other cell that does not contain flowers by moving through cells that do not contain flowers.

It is guaranteed that there is at least one hole, and the number of holes in the garden does not exceed $100$.

输出格式

In the first line, print a single integer $x$ ($1 \leq x \leq n \cdot m$) --- the number of optimal positions.

In each of the next $x$ lines, print the optimal positions ($x;y$) for waiting for the mole ($1 \le x \le n$, $1 \le y \le m$).

Positions can be printed in any order.

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} :::

Let $k$ be the number of holes in the garden.

• ($6$ points): $n = 1, m = 2$;
• ($9$ points): $n = 1$;
• ($15$ points): $k = 1, n \cdot m \le 5 \cdot 10^3$;
• ($22$ points): $n \cdot m \le 5 \cdot 10^3$;
• ($17$ points): $k = 1$;
• ($31$ points): without additional restrictions.