## COCI '08 Contest 1 #3 Mravojed

View as PDF

Points: 10
Time limit: 0.6s
Memory limit: 32M

Problem type

Archeologists recently found the remains of Greco-Roman architecture. The location can be modeled as a grid of 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 Specification

The first line contains two integers and , the size of the location.

Each of the next lines contains a string of 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 Specification

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

Note: The test data will guarantee that a solution always exists, although it may not necessarily be unique.

#### 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