E2. Рисование звезд (усложненная редакция)
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Звезда — это фигура на клетчатом поле следующего вида: символ звездочка '*' в центре фигуры и четыре луча (влево, вправо, вверх и вниз) одинаковой положительной длины. Размером звезды является длина ее лучей. Размер звезды должен быть строго положительным (то есть лучи длины $$$0$$$ недопустимы).

Пусть пустые клетки обозначены как '.'. Тогда, например, следующие фигуры являются звездами:

Левая фигура — звезда размера $$$1$$$, средняя фигура — звезда размера $$$2$$$ и правая фигура — звезда размера $$$3$$$.

Задано прямоугольное поле размера $$$n \times m$$$, состоящее из звездочек '*' и точек '.'. Строки пронумерованы от $$$1$$$ до $$$n$$$, столбцы пронумерованы от $$$1$$$ до $$$m$$$. Ваша задача — нарисовать это поле при помощи любого количества звезд или понять, что это невозможно сделать. Звезды могут пересекаться, вкладываться и даже совпадать друг с другом. Количество звезд в ответе не может превышать $$$n \cdot m$$$. Каждая из звезд должна находиться строго внутри поля. Вы можете использовать звёзды как одинаковых так и различных размеров.

В этой задаче нет необходимости минимизировать количество звезд. Необходимо найти любой способ нарисовать заданное поле при помощи не более, чем $$$n \cdot m$$$ звезд.

Входные данные

Первая строка входных данных содержит два целых числа $$$n$$$ и $$$m$$$ ($$$3 \le n, m \le 1000$$$) — размер заданного поля.

Следующие $$$n$$$ строк содержат $$$m$$$ символов каждая, $$$i$$$-я строка описывает $$$i$$$-ю строку поля. Гарантируется, что поле состоит только из символов '*' и '.'.

Выходные данные

Если невозможно нарисовать заданное поле только при помощи некоторого количества звезд , выведите «-1».

Иначе в первой строке выедите $$$k$$$ ($$$0 \le k \le n \cdot m$$$) — количество звезд, необходимое, чтобы нарисовать заданное поле. Следующие $$$k$$$ строк должны содержать по три целых числа каждая — $$$x_j$$$, $$$y_j$$$ и $$$s_j$$$, где $$$x_j$$$ это номер строки центрального символа звезды, $$$y_j$$$ — номер столбца центрального символа звезды и $$$s_j$$$ — размер звезды. Каждая из звезд должна находиться строго внутри поля.

Примеры
Входные данные
6 8
....*...
...**...
..*****.
...**...
....*...
........
Выходные данные
3
3 4 1
3 5 2
3 5 1
Входные данные
5 5
.*...
****.
.****
..**.
.....
Выходные данные
3
2 2 1
3 3 1
3 4 1
Входные данные
5 5
.*...
***..
.*...
.*...
.....
Выходные данные
-1
Входные данные
3 3
*.*
.*.
*.*
Выходные данные
-1
Примечание

В первом примере вывод

2
3 4 1
3 5 2

тоже является корректным.