Кріт#265
Після важкого дослідження Антон вирішив відпочити на своїй дачі. У нього там є прекрасний сад з багатьма різними квітами. Але от халепа, по приїзду він побачив значну кількість дірок в землі. Це кріт!
Тепер, озброївшись лопатою, Антон чекатиме на крота. Кріт може вилізти в будь-якій дірці. Антон хоче вибрати позицію так, щоб в найгіршому випадку він біг до крота мінімальну кількість часу.
Сад можна представити як матрицю n \times m, де — це кількість рядків, а — кількість стовпців. Рядки нумеруються зверху вниз від до . Стовпці нумеруються зліва направо від до . Тобто, клітинка з індексом знаходиться в лівому верхньому куті.
Кожна клітинка саду a_{i, j} описує стан цієї клітинки:
a_{i, j} = «.» — ця клітинка не містить квіт та дірок;
a_{i, j} = «F» — ця клітинка містить квіти;
a_{i, j} = «H» — ця клітинка містить дірку.
Антон також знає, що кількість дір не перевищує .
Як людина, яка вклала багато часу в ці квіти, ваше серце не зможе винести топтання квітів. Тому Вам треба прокладати шлях таким чином, щоб він не проходив через них.
За один момент часу Антон може переміститися з позиції у будь-яку з наступних позицій: (x-1,y), (x+1,y), (x,y-1), (x,y+1) за умов, що нова позиція не містить квітів та знаходиться всередині саду.
Знайдіть всі позиції (), з яких Антон буде бігти до кротів в найгіршому випадку мінімальну кількість часу.
Перший рядок містить два цілі числа , (1 \le n \cdot m \le 2 \cdot 10^5) — довжина і ширина саду.
Наступні рядків містять по символів кожен — опис саду.
Гарантується, що з кожної клітинки, що не містить квіти, можна дістатися до будь-якої іншої клітинки, що не містить квіти, рухаючись по клітинках, що не містять квіти.
Гарантується, що існує хоча б одна дірка, і кількість дірок в саду не перевищує .
У першому рядку виведіть одне ціле число (1 \leq x \leq n \cdot m) — кількість оптимальних позицій.
У кожному з наступних рядків виведіть оптимальні позиції () для чекання крота (1 \le x \le n, 1 \le y \le m).
Позиції можна виводити у будь-якій послідовності.
Приклад
Приклад 1
Вище наведено перший приклад і відмічено оптимальні позиції для очікування.
Нехай — кількість дірок в саду.
( балів): n = 1, m = 2;
( балів): n = 1;
( балів): k = 1, n \cdot m \le 5 \cdot 10^3;
( бали): n \cdot m \le 5 \cdot 10^3;
( балів): k = 1;
( бал): без додаткових обмежень.