FRAKTAL - konkurs programistyczny

Małgosia na prostokątnej tkaninie o rozmiarach m × n cm wyszyła pewną liczbę gwiazdek o rozmiarach 1 × 1 cm. Kiedy jej kolega Jaś zobaczył ten przepiękny haft, zapragnął mieć taki sam.

Nasz bohater posiada maszynę do haftowania. Urządzenie to reprezentuje tkaninę jako tabelę o m wierszach i n kolumnach. Wiersze numerowane są od góry do dołu, od 1 do m. Kolumny numerowane są od lewej do prawej, od 1 do n. Komórka tabeli odpowiada fragmentowi tkaniny o rozmiarze 1 × 1 cm. Maszyna może wykonać maksymalnie m × n operacji haftowania. W ramach pojedynczej operacji urządzenie wyszywa gwiazdkę w kolumnie x wiersza y, a następnie po r gwiazdek:

• pionowo w górę
• pionowo w dół
• poziomo w lewo
• poziomo w prawo

Wartość r musi być dodatnią liczbą całkowitą. W przypadku, gdy w jakiejś komórce był już wykonany haft, maszyna ją pomija. Operacja powodująca próbę wyszycia gwiazdki poza obszarem tkaniny kończy się uszkodzeniem urządzenia.

Przykładowy haft dla r = 1

.*.
***
.*.

Przykładowy haft dla r = 3

...*...
...*...
...*...
*******
...*...
...*...
...*...

Jaś posiada taką samą tkaninę jak Małgosia. Odpowiedz na pytanie. Czy nasz bohater jest w stanie, za pomocą posiadanej maszyny, odwzorować haft swojej koleżanki?

Wejście

W pierwszej linii wejścia znajdują się dwie liczby całkowite m ∈ [3, 1000] i n ∈ [3, 1000] określające rozmiar tkaniny Małgosi.

W kolejnych m wierszach znajduje się po n znaków opisujących zawartość kolejnych cm² tkaniny. Znak * oznacza, że na danym cm² Małgosia wyszyła gwiazdkę. Znak . oznacza, że dany cm² nie był zmieniany.

Wyjście

Jeżeli Jaś nie jest w stanie, za pomocą posiadanej maszyny, odwzorować haftu Małgosi na wyjściu należy wypisać -1.

W przeciwnym wypadku w pierwszej linii wyjścia należy wypisać liczbę operacji haftowania do wykonania, zaś w kolejnych ich opis. Każda operacja powinna zostać scharakteryzowana za pomocą 3 liczb całkowitych x, y i r oznaczających odpowiednio współrzędne komórki, w której rozpoczyna się wyszywanie oraz długość promieni.

Jeżeli istnieje wiele rozwiązań, wypisz dowolne z nich.

Przykład 1

Wejście:

7 5
.....
.*.*.
*****
.*.*.
*****
.*.*.
.....

Wyjście:

4
2 3 1
4 3 1
2 5 1
4 5 1

Przykład 2

Wejście:

4 6
......
.****.
.****.
......

Wyjście:

-1