Кріт
ліміт часу на тест
1 second
ліміт використання пам'яті на тест
256 megabytes
введення
standard input
виведення
standard output

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

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

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

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

Антон також знає, що кількість дір не перевищує $$$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 \leq x \leq 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$$$ бал): без додаткових обмежень.

Приклади

Вхідні дані
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

Пояснення

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