Description

Archaeologists have recently discovered the remains of Greek and Roman buildings. The site can be modeled as a grid of $r \times c$ square cells. For each cell, the archaeologists have determined whether there is a remain.

After a detailed examination, they concluded that the site contains two buildings from different periods, and the floor plan of each building is a square.

Since the buildings are from different periods, their floor plans may overlap.

Determine the possible position and size (the side length of the square area it covers) for each building.

Input Format

The first line contains two integers $r$ and $c$, representing the number of rows and columns of the site.

The next $r$ lines each contain $c$ characters. . means no remain is found in that cell, and x means a remain is found in that cell.

Output Format

For each building, output the coordinates of its top-left corner ($2$ numbers) and its side length ($1$ number). Separate every two numbers with a space.

3 3
xx.
xxx
...

1 1 2
2 3 1

4 6
xx....
xx.xxx
...xxx
...xxx

1 1 2
2 4 3

5 5
.....
xxx..
xxxx.
xxxx.
.xxx.

2 1 3
3 2 3

Hint

Hint

The solution may not be unique.

Constraints

For $100\%$ of the testdata, a solution is guaranteed to exist, and $1 \leq r \leq 100,1 \leq c \leq 100$.

Notes

Translated from COCI2008-2009 CONTEST #1 MRAVOJED. Translator:

Acknowledgements

Thanks to

Translated by ChatGPT 5