Кріт

Після важкого дослідження Антон вирішив відпочити на своїй дачі. У нього там є прекрасний сад з багатьма різними квітами. Але от халепа, по приїзду він побачив значну кількість дірок в землі. Це кріт!

Тепер, озброївшись лопатою, Антон чекатиме на крота. Кріт може вилізти в будь-якій дірці. Антон хоче вибрати позицію так, щоб в найгіршому випадку він біг до крота мінімальну кількість часу.

Сад можна представити як матрицю $n\times m$, де $n$ — це кількість рядків, а $m$ — кількість стовпців. Рядки нумеруються зверху вниз від $1$ до $n$. Стовпці нумеруються зліва направо від $1$ до $m$. Тобто, клітинка з індексом $(1;1)$ знаходиться в лівому верхньому куті.

Кожна клітинка саду $a_{i,j}$ описує стан цієї клітинки:

• $a_{i,j}$ = «.» — ця клітинка не містить квіт та дірок;

• $a_{i,j}$ = «F» — ця клітинка містить квіти;

• $a_{i,j}$ = «H» — ця клітинка містить дірку.

Антон також знає, що кількість дір не перевищує $100$.

Як людина, яка вклала багато часу в ці квіти, ваше серце не зможе винести топтання квітів. Тому Вам треба прокладати шлях таким чином, щоб він не проходив через них.

За один момент часу Антон може переміститися з позиції $(x,y)$ у будь-яку з наступних позицій: $(x-1,y)$, $(x+1,y)$, $(x,y-1)$, $(x,y+1)$ за умов, що нова позиція не містить квітів та знаходиться всередині саду.

Знайдіть всі позиції ($x;y$), з яких Антон буде бігти до кротів в найгіршому випадку мінімальну кількість часу.

Вхідні дані

Перший рядок містить два цілі числа $n$, $m$ ($1\le n\cdot m\le 2\cdot 10^5$) — довжина і ширина саду.

Наступні $n$ рядків містять по $m$ символів кожен — опис саду.

Гарантується, що з кожної клітинки, що не містить квіти, можна дістатися до будь-якої іншої клітинки, що не містить квіти, рухаючись по клітинках, що не містять квіти.

Гарантується, що існує хоча б одна дірка, і кількість дірок в саду не перевищує $100$.

Вихідні дані

У першому рядку виведіть одне ціле число $x$ ($1\le x\le n\cdot m$) — кількість оптимальних позицій.

У кожному з наступних $x$ рядків виведіть оптимальні позиції ($x;y$) для чекання крота ($1\le x\le n$, $1\le y\le m$).

Позиції можна виводити у будь-якій послідовності.

Приклади

Примітка

Вище наведено перший приклад і відмічено оптимальні позиції для очікування.

Оцінювання

Нехай $k$ — кількість дірок в саду.

1. ($6$ балів): $n=1,m=2$;

2. ($9$ балів): $n=1$;

3. ($15$ балів): $k=1,n\cdot m\le 5\cdot 10^3$;

4. ($22$ бали): $n\cdot m\le 5\cdot 10^3$;

5. ($17$ балів): $k=1$;

6. ($31$ бал): без додаткових обмежень.