Middle Earth Technical University Programming Contest

View as PDF

Submit solution


Points: 1
Time limit: 1.0s
Memory limit: 256M

Problem types

Gizem and Deniz are attending Middle Earth Technical University's \(24^{th}\) Annual Programming Contest. They are struggling with a question in the qualification round, given below:

You are given a rectangular area of height \(\mathbf{h}\) and width \(\mathbf{w}\) comprised of black and white unit squares. Squares are numbered from \(\mathbf{0}\) to \(\mathbf{h-1}\) for the rows and \(\mathbf{0}\) to \(\mathbf{w-1}\) for the columns. Given this area, find the coordinates of the upper-left and bottom-right corners of the largest square region consisting of only white unit squares in terms of surface area.

If there exists more than one such square region, you can output either one.

Coordinates of a unit square should be given with respect to the unit square on the upper-left corner of the rectangular region. For instance, the square that is to the right of the one on the upper-left corner (i.e. the second square from left on top row) has coordinates \((1, 0)\).

The grid includes at least one white square.

Gizem and Deniz are really eager to participate in the final round of the contest. Can you help them with the question they are struggling with?

Input

You will be given the size of the rectangular region in the first line: \(\mathbf{h}\) and \(\mathbf{w}\) for height and width, respectively.

For the following \(\mathbf{h}\) lines, you will be given \(\mathbf{w}\) characters in each line that describes a row of the rectangular region. Characters can be "W" for white unit squares and "B" for black unit squares.

  • \(1 \leq \mathbf{h, w} \leq 500\)

Output

For \(p_1 = (x_1, y_1)\) and \(p_2 = (x_2, y_2)\), that are the coordinates of the upper-left and the bottom-right corners of the requested square region. \(x\) is column number and \(y\) is the row number. You are required to print four numbers: \(x_1\ y_1\ x_2\ y_2\).

Example

Input:

4 5
W B B W B
B W W B W
B W W W W
B B W B W

Output:

1 1 2 2

Input:

4 10
W W W W W B W B B W 
B W W W W W B W B W 
W W W W W W W W W B 
B W W W W W B B W W

Output:

1 0 4 3

Explanation

Input 1

The biggest square which is comprised of white squares is between the points (1, 1) and (2, 2). Its side length is 2 and its area is 4.

Input 2

The biggest square which is comprised of white squares is between the points (1, 0) and (4, 3). Its side length is 4 and its area is 16.