COCI 2008/2009, Contest #1

Task MRAVOJED

Archeologists recently found the remains of Greco-Roman architecture. The location can be modeled as a grid of R·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 ≤ R ≤ 100) and C (1 ≤ C ≤ 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 of the building.
Note: The test data will guarantee that a solution always exists, although it may not necessarily be unique.

Examples

Input

3 3
xx.
xxx
...

Output

1 1 2
2 3 1

Input

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

Output

1 1 2
2 4 3

Input

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

Output

2 1 3
3 2 3

All Submissions
Best Solutions


Point Value: 15
Time Limit: 1.00s
Memory Limit: 32M
Added: Oct 18, 2008

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

ilovepi on Mar 19, 2011 - 5:22:42 pm UTC Typo
  • (0/1)
Instead of string, it says 'Each of the next R lines contains a strong of C characters'
Lol.