UFPT2015C - Gold Leaf

Gold Leaf is a very thin layer of gold, with a paper backing. If the paper gets folded and then unfolded, the gold leaf will stick to itself more readily than it will stick to the paper, so there will be patches of gold and patches of exposed paper. Note that the gold leaf will always stick to itself, rather than the paper. In the following example, the paper was folded along the dashed line. Notice how the gold leaf always sticks to one side or the other, never both.

Gold Leaf

Consider a crude digital image of a sheet of gold leaf. If the area covered by a pixel is mostly gold, that will be represented by a ‘#’. If it’s mostly exposed paper, it will be represented by a ‘.’. Determine where the sheet was folded. The sheet was folded exactly once, along a horizontal, vertical, or 45 degree or 135 degree diagonal line. If the fold is horizontal or vertical, it is always between rows/columns. If the fold is diagonal, then the fold goes through a diagonal line of cells, and the cells along the fold are always ‘#’.

Input

Each input will consist of a single test case. Note that your program may be run multiple times on different inputs. Each test case will begin with a line with two integers, n and m (2 ≤ n, m ≤ 25), where n is the number of rows, and m is the number of columns of the image. Each of the next n lines will contain exactly m characters, all of which will be either ‘#’ or ‘.’. This represents a crudely collected digital image of the sheet of gold leaf. There is guaranteed to be at least one ‘.’, and there is guaranteed to be a solution.

Output

Output a single line with four integers, with a single space between integers, indicating the places where the fold hits the edges of the paper. Output no extra spaces. Output them in this order: r1 c1 r2 c2 where (r1, c1) and (r2, c2) are row/column coordinates (r = row, c = column). The top left character of the image is (1,1) and the bottom right is (n, m).

If the fold is horizontal or diagonal, list the left coordinates before the right. If the fold is vertical, list the top coordinates before the bottom.

If the fold is horizontal, use the coordinates above the fold. If the fold is vertical, use the coordinates to the left of the fold. If the fold is diagonal, use the coordinates of the edge pixels that the fold goes through.

If more than one fold is possible, choose the one with the smallest first coordinate, then the smallest second coordinate, then third, then fourth.

Example

Input:
8 10
#.#..##..#
####..####
###.##....
...#..####
....##....
.#.##..##.
##########
########## 

Output:
3 1 3 10
Input:
5 20
###########.#.#.#.#.
###########...#.###.
##########..##.#..##
###########..#.#.##.
###########.###...#.

Output:
1 15 5 15
Input:
5 5
.####
###.#
##..#
#..##
#####

Output:
4 1 1 4

Added by:Cormac
Date:2015-09-20
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 GOSU JS-MONKEY
Resource:2014 ACM ICPC Southeast Regional Programming Contest

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.