Hole in the Wall

A square wall of size $N \times N$ is built from $N^2/2$ bricks that fit tightly against each other, and $N$ is even. Every brick has size $2 \times 1$ and the bricks are numbered from 1 to $N^2/2$. Some bricks lie horizontally, the rest lie vertically. The wall has no gaps, so every cell of the $N \times N$ square is covered by exactly one brick. In the picture below, two cells that carry the same number are the two halves of one brick.

A rectangular hole has to be cut into the wall to fit a window. The hole must meet three requirements.

1. Its sides are parallel to the sides of the wall.
2. The hole touches no side of the wall, so it lies strictly inside the wall.
3. No brick is cut, so the border of the hole runs only along borders of bricks.

Find a hole of maximum area.

The first line contains the integer $N$, the length of a side of the wall. Each of the next $N$ lines contains $N$ integers, the brick numbers of the cells of that row from left to right. Two cells carry the same number exactly when they belong to the same brick.

Print five integers separated by single spaces: the area of a largest legal hole, the row and the column of its upper left cell, and the row and the column of its lower right cell. Rows are numbered 1 to $N$ from top to bottom and columns 1 to $N$ from left to right, so the upper left cell of the wall is $(1, 1)$.

Several rectangles can reach the maximum area. Print the one whose quadruple $(r_1, c_1, r_2, c_2)$ is lexicographically smallest: take the smallest $r_1$, among those the smallest $c_1$, then the smallest $r_2$, then the smallest $c_2$.

If the wall admits no legal hole, print 0 0 0 0 0.

• $4 \le N \le 1000$, and $N$ is even.
• Every number from 1 to $N^2/2$ appears on exactly two cells, and those two cells share a side.

In the first example the largest hole has area 8. It is cut by removing the bricks numbered 3, 6, 7 and 8.