Problem H. Hype spreading

Author:A. Klenin   Time limit:1 sec
Input file:input.txt   Memory limit:256 Mb
Output file:output.txt  

Statement

One famous car race takes place on a stadium with a racetrack. Spectators watching the race sit on a stand consisting of H rows with W seats each. During the race, some seats are occupied by spectators, and others are empty.

Marketing research demonstrated that if one spectator will loudly shout out a nicely rhymed slogan, spectators on seats located immediately to the left, right, above and below him will repeat it. Their neighbors, in turn, will catch up, and the slogan will spread throughout the stand.

An advertisement company invented a new slogan and wants it to spread among as many spectators as possible. To simulate "spontaneous" appearance of the slogan the company hired an agent who will move to one of the unoccupied seats and shout the slogan from there.

You program must determine the position of the agent which will result in maximum slogan penetration.

Input file format

Input file contains integers W H in the first line, followed by H lines of W characters each.

Each character is either a '.' (ASCII 46) or '#' (ASCII 35), denoting free and occupied seat correspondingly.

There is at least one free seat.

Output file format

Output file must contain two integers — x y, denoting seat number and row number for the agent to take. Rows are numbered starting from 1, top to bottom. Seats are numbered starting from 1, left to right. If there are several optimal solutions, output any of them.

Constraints

2 ≤ W, H ≤ 2000

Sample tests

No. Input file (input.txt) Output file (output.txt)
1
2 2
#.
.#
2 1
2
5 5
..#.#
..###
#..##
#.##.
#....
2 4
3
6 4
######
.....#
..##.#
...#.#

3 2

0.172s 0.017s 13