Finding Crosses

Interview

Time limit2sMemory limit512 MB

Summary

Given a grid of stars and dots, decide whether it can be covered exactly by overlapping plus-shaped crosses, and if so output which crosses to draw.

Level: Medium6 of 10
Topics: Implementation, Brute force, Simulation, Greedy
Solved: No attempts yet

Problem

A cross has a * in the center and * cells extending up, down, left, and right by the same length. The size of a cross is the number of * cells extending in each of the four directions from the center. The size of a cross must be at least 1.

The figure below shows crosses of size 1, 2, and 3, where empty cells are ..

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

A grid of size N×M consisting of . and * is given. Determine whether the grid can be formed using only crosses. Crosses may overlap. The number of crosses used must be at most N×M. The rows of the grid are numbered 1 from the top, and the columns are numbered 1 from the left.

Input

The first line gives the size of the grid N, M (3 ≤ N, M ≤ 100). The next N lines give the state of the grid.

Output

If the given grid cannot be formed using only crosses, print -1.

Otherwise, print the number of crosses needed k (0 ≤ k ≤ N×M). The next k lines give the information x, y, s of each cross to draw, one per line. x is the row number of the center of the cross, y is the column number, and s is the size of the cross.

If there are multiple possible answers, print any of them.

Examples4

Example 1

Input

6 8
....*...
...**...
..*****.
...**...
....*...
........

Expected output

Example 2

Input

5 5
.*...
****.
.****
..**.
.....

Expected output

Example 3
Input
```
5 5
.*...
***..
.*...
.*...
.....
```
Expected output
```
-1
```
Example 4
Input
```
3 3
*.*
.*.
*.*
```
Expected output
```
-1
```