Звезда — это фигура на клетчатом поле следующего вида: символ звездочка '*' в центре фигуры и четыре луча (влево, вправо, вверх и вниз) одинаковой положительной длины. Размером звезды является длина ее лучей. Размер звезды должен быть строго положительным (то есть лучи длины \(0\) недопустимы).
Пусть пустые клетки обозначены как '.'. Тогда, например, следующие фигуры являются звездами:
Левая фигура — звезда размера \(1\), средняя фигура — звезда размера \(2\) и правая фигура — звезда размера \(3\). Задано прямоугольное поле размера \(n \times m\), состоящее из звездочек '*' и точек '.'. Строки пронумерованы от \(1\) до \(n\), столбцы пронумерованы от \(1\) до \(m\). Ваша задача — нарисовать это поле при помощи любого количества звезд или понять, что это невозможно сделать. Звезды могут пересекаться, вкладываться и даже совпадать друг с другом. Количество звезд в ответе не может превышать \(n \cdot m\). Каждая из звезд должна находиться строго внутри поля. Вы можете использовать звёзды как одинаковых так и различных размеров.
В этой задаче нет необходимости минимизировать количество звезд. Необходимо найти любой способ нарисовать заданное поле при помощи не более, чем \(n \cdot m\) звезд.
Выходные данные
Если невозможно нарисовать заданное поле только при помощи некоторого количества звезд , выведите «-1».
Иначе в первой строке выедите \(k\) (\(0 \le k \le n \cdot m\)) — количество звезд, необходимое, чтобы нарисовать заданное поле. Следующие \(k\) строк должны содержать по три целых числа каждая — \(x_j\), \(y_j\) и \(s_j\), где \(x_j\) это номер строки центрального символа звезды, \(y_j\) — номер столбца центрального символа звезды и \(s_j\) — размер звезды. Каждая из звезд должна находиться строго внутри поля.
Примечание
В первом примере вывод
2
3 4 1
3 5 2
тоже является корректным.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6 8
....*...
...**...
..*****.
...**...
....*...
........
|
3
3 4 1
3 5 2
3 5 1
|
|
2
|
5 5
.*...
****.
.****
..**.
.....
|
3
2 2 1
3 3 1
3 4 1
|
|
3
|
5 5
.*...
***..
.*...
.*...
.....
|
-1
|
|
4
|
3 3
*.*
.*.
*.*
|
-1
|