Greco-Roman Architecture

Time limit1sMemory limit128 MB

Summary

Given a grid marked with traces of two overlapping axis-aligned square floor plans, find the top-left corner and size of each of the two squares whose union equals the marked cells.

Level: Medium7 of 10
Topics: Brute force, Geometry, Implementation
Solved: No attempts yet

Problem

Archaeologists recently found the remains of Greco-Roman architecture. The site can be modeled as a grid with R rows and C columns, and each cell is marked according to whether a building trace was found there.

They determined that two buildings from different periods once stood on the site. The floor plan of each building was an axis-aligned square.

Because the two buildings were built in different periods, their floor areas may overlap. Find the positions and sizes of two square floors whose union matches the marked cells.

Input

The first line contains R and C, the size of the site. (1 ≤ R ≤ 100, 1 ≤ C ≤ 100)

Each of the next R lines contains a string of length C. Each character is either . or x. A . means there was no building trace in that cell, and an x means there was a building trace.

Output

Print the top-left coordinate and side length of each building floor, one building per line. Each line must have the form row column size.

Every input is guaranteed to have at least one valid answer.

Examples3

Example 1
Input
```
3 3
xx.
xxx
...
```
Expected output
```
1 1 2
2 3 1
```

Example 2

Input

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

Expected output

1 1 2
2 4 3

Example 3

Input

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

Expected output

2 1 3
3 2 3