Problem 1: Nikhil's Birthday Cake, *(K Narayan Kumar, CMI)*

It is Nikhil's birthday and he has to cut his birthday cake. It is a square cake. He has to make one horizontal and one vertical cut to divide the cake into four pieces. Then, his sister, his father and his mother get to choose their pieces. Finally, he gets the last piece left on the plate.

If it were a simple cake, it would be best for Nikhil to cut
it into four equal quarters. However, the cake is divided into
*N ×N* squares. Some of these squares are covered
with chocolate chips. Everyone in his family loves chocolate and
since everyone else gets to choose their piece before he does, he
is likely to get the piece with the least number of squares
covered with chocolate chips. Nikhil is more interested in the
chocolate chips than the cake itself, so he would like to cut the
cake in such a way that he is guaranteed to get as many squares
covered with chocolate chip as possible.

He has been told that he his cuts must not pass through any of the squares (that is, the cuts must be along the boundaries of the squares).

Suppose the cake looks like:

. . # . . # . . . # # . . # . . . . . . . . # . . # # . . . . . . . # . # . . . . . . . . . # . . . . . . . . . . . # . . # . .

where a # denotes a square covered with chocolate chips and a . denotes a square with no chocolate chips on it. Here are two possible ways in which Nikhil could cut the cake.

. . # . .|# . . . . # .|. # . . . # # . .|# . . . # # .|. # . . . . . . .|. # . . . . .|. . # . . # # . .|. . . -------|------- ---------|----- . # # .|. . . . . . # . #|. . . . . # .|# . . . . . . . .|. # . . . . .|. . # . . . . . .|. . . . . . .|. . . . . . # . .|# . . . . # .|. # . .

With the first set of cuts, he will end up with the bottom-right piece containing just two squares covered with chocolate chips. On the other hand, if he cuts it as indicated in the second figure then he is guaranteed to get three squares covered with chocolate chips. You can verify that this is the best he can do.

Your task is to help Nikhil determine the best way to cut the cake to maximize his share of squares covered with chocolate chips.

Input format

The first line of input contains a single integer *N*
indicating the number of squares in each line. This is followed
by *N* lines of input each containing *N*
characters (each of which is either a # or a .).

Output format

The first line of the output contains a single integer *M*
indicating the maximum number of squares covered with chocolate
chips that Nikhil can get. This followed by a line containing two
integers *R* and *C*, describing a way to cut the
cake so that he gets *M* squares covered with chocolate
chips. The number *R* indicates that the horizontal cut is
placed between the *R ^{th}* and

Test data

For all inputs, *N* ≤ 2000. Further, you may
assume that *N* ≤ 50 in 80% of the inputs.

Example

We now illustrate input and output formats using the example described above.

Sample input

8 ..#..#.. .##..#.. ......#. .##..... ..#.#... ......#. ........ ..#..#..

Sample output

3 3 4

Copyright (c) IARCS 2003-2020; Last Updated: 10 Nov 2005