Беси любит разгадывать кроссворды.
Однако её сестра Эльза пролила молоко на кроссворд,
и теперь Вам предстоит его восстановление (номеров
загаданных слов).
Вам даётся кроссворд, как решётка N*M (3 <= N <=
50, 3 <= M <= 50). Некоторые из клеток пусты (обычно они
белые), а некоторые заблокированы (обычно они чёрные).
Теперь процесс присвоения номеров загаданным словам -
это простой процесс из двух логических шагов:
Шаг 1: Для каждой ячейки мы определяем, начинает ли она
горизонтальное загаданное слово, или вертикальное
загаданное слово. Чтобы ячейка начинала горизонтальное
загаданное слово, нужно, чтобы её левая соседка была
заблокированной ячейкой или лежала вне кроссворда и две
клетки вправо от неё должны быть пустыми. (То есть
горизонтальное загаданное слово всегда содержит 3 или более
символов). Правила для ячейки, начинающей вертикальное
загаданное слово аналогичны: ячейка сверху должна быть
заблокирована или вне кроссворда и две клетки вниз
должны быть пустыми.
Шаг 2: Мы назначаем номер каждой ячейке, которая начинает
слово, последовательно от 1 в том же порядке, в котором
мы читаем книгу.
В первой строке назначаем числа слева направо, затем во
второй строке назначаем числа слева направо и т.д.
Числа назначаются только ячейкам, начинающим слова.
Например, рассмотрим кроссворд, где пустые ячейки отмечены
символами '.'. а блокированные ячейки отмечены символами '#'.
...
#..
...
..#
.##
Ячейки, которым могут быт присвоены номера
горизонтальных или вертикальных загаданных слов
помечены символами !.
!!!
#..
!..
..#
.##
Номера должны быть таковы:
123
#..
4..
..#
.##
Заметим, что кроссворд, описанный во входных данных,
может не удовлетворять ограничениям в обычно публикуемых
кроссвордах. Например, некоторые пустые ячейки могут
не быть частью никакого слова.
Формат входных данных
Первая строка ввода содержит N и M, разделённые
одиночным пробелом.
Последующие N строк ввода описывают строки
решётки. Каждая состоит из M символов, каждый из которых
либо '.' (пустая ячейка) либо '#' (блокированная ячейка).
Формат выходных данных
На первой строке выведите количество загаданных слов.
На каждой из оставшихся строк выведите строку и колонку
дающую позицию одного слова (в порядке, описанном выше).
Верхняя левая ячейка имеет позицию (1,1). Нижняя правая
ячейка имеет позицию (N,M).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 3
...
#..
...
..#
.##
|
4
1 1
1 2
1 3
3 1
|