Після важкого дослідження Антон вирішив відпочити на своїй дачі. У нього там є прекрасний сад з багатьма різними квітами. Але от халепа, по приїзду він побачив значну кількість дірок в землі. Це кріт!
Тепер, озброївшись лопатою, Антон чекатиме на крота. Кріт може вилізти в будь-якій дірці. Антон хоче вибрати позицію так, щоб в найгіршому випадку він біг до крота мінімальну кількість часу.
Сад можна представити як матрицю $$$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$$$ — кількість дірок в саду.
3 4HF.F..HFFF.F
2 2 1 2 2
4 9......FFH.F..FHFF.HF........FHF..FFF
2 1 6 3 4
![]() |