Problem Description

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

After a detailed examination of the artifacts, they concluded that the site contains two buildings from different periods, both of which are square in plan.

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

Determine the possible positions and sizes (side length of the square plan) for each building.

Input Format

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

The following $r$ lines each contain $c$ characters, where . indicates no remains were found, and x indicates remains were found.

Output Format

For each building, output the coordinates of the top-left vertex (2 numbers) and its side length (1 number), with each number separated by a space.

Sample Input and Output

Sample Input #1

3 3
xx.
xxx
...

Sample Output #1

1 1 2
2 3 1

Sample Input #2

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

Sample Output #2

1 1 2
2 4 3

Sample Input #3

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

Sample Output #3

2 1 3
3 2 3

Notes/Hints

• The solution may not be unique.
• For $100\%$ of the data, a solution is guaranteed, with $1 \leq r \leq 100$ and $1 \leq c \leq 100$.

The problem is translated from COCI2008-2009 CONTEST #1 MRAVOJED, translated by @mnesia.

Special thanks to @y0y68 for providing the SPJ.

见题面 Input 部分

见题面 Output 部分