Hide

Problem K
Mravojed

Archeologists recently found the remains of Greco-Roman architecture. The location can be modeled as a grid of $R \cdot C$ square cells. For each of the cells, archeologists have determined if some building was there or if the cell has always been empty.

After examining the artifacts in detail, they concluded that the location contains two buildings from different periods in time, and that the floor plans of both buildings are of square shape.

Because the buildings were from different periods in time, it is possible that their floor plans overlap. Determine the possible location and size (length of the side of the square occupied by the floor plan) for each building.

Input

The first line contains two integers $R$ ($1 \le R \le 100$) and $C$ ($1 \le C \le 100$), the size of the location.

Each of the next $R$ lines contains a string of $C$ characters ‘.’ (dot) or ‘x’ (lowercase letter). The character ‘.’ means that nothing was found in that cell, while ‘x’ indicates that there was a building there.

Output

For each of the two buildings, output on a single line the row and column of its upper left corner, and the size (side length) of the building.

Note: the test data will be such that a solution always exists, although it may not be unique. If there is more than one solution, any one will be accepted.

Sample Input 1 Sample Output 1
3 3
xx.
xxx
...
1 1 2
2 3 1
Sample Input 2 Sample Output 2
4 6
xx....
xx.xxx
...xxx
...xxx
1 1 2
2 4 3
Sample Input 3 Sample Output 3
5 5
.....
xxx..
xxxx.
xxxx.
.xxx.
2 1 3
3 2 3

Please log in to submit a solution to this problem

Log in