벽에 뚫는 구멍

한 변의 길이가 $N$인 정사각형 벽이 $N^2/2$개의 벽돌로 빈틈없이 채워져 있다. $N$은 짝수이고, 벽돌은 모두 $2 \times 1$ 크기이며 1번부터 $N^2/2$번까지 번호가 붙어 있다. 일부는 가로로 놓였고 나머지는 세로로 놓였다. 벽에 빈 곳은 없어서 $N \times N$의 모든 칸이 정확히 벽돌 하나에 덮인다. 아래 그림에서 같은 번호가 적힌 두 칸은 한 벽돌의 두 조각이다.

창을 달려고 벽에 직사각형 구멍을 뚫으려 한다. 구멍은 다음 세 조건을 지켜야 한다.

1. 구멍의 변은 벽의 변과 평행하다.
2. 구멍은 벽의 어느 변에도 닿지 않는다. 즉 벽 안쪽에 완전히 들어간다.
3. 어떤 벽돌도 자르지 않는다. 즉 구멍의 경계는 벽돌의 경계만 따라간다.

넓이가 가장 큰 구멍을 구하라.

첫째 줄에 벽의 한 변 길이 $N$이 주어진다. 다음 $N$개 줄에는 줄마다 그 행의 칸을 왼쪽부터 차례로 덮는 벽돌 번호 $N$개가 주어진다. 두 칸의 번호가 같다는 것은 두 칸이 같은 벽돌에 속한다는 뜻이다.

넓이가 최대인 구멍 하나에 대해 넓이, 왼쪽 위 칸의 행 번호와 열 번호, 오른쪽 아래 칸의 행 번호와 열 번호를 공백 하나로 구분한 정수 다섯 개로 출력한다. 행은 위에서 아래로 1번부터 $N$번, 열은 왼쪽에서 오른쪽으로 1번부터 $N$번이므로 벽의 왼쪽 위 칸은 $(1, 1)$이다.

넓이가 최대인 직사각형이 여러 개면 $(r_1, c_1, r_2, c_2)$가 사전순으로 가장 작은 것을 출력한다. 즉 $r_1$이 가장 작은 것을 고르고, 그중에서 $c_1$이 가장 작은 것, 그다음 $r_2$가 가장 작은 것, 마지막으로 $c_2$가 가장 작은 것을 고른다.

조건을 만족하는 구멍이 하나도 없으면 0 0 0 0 0을 출력한다.

• $4 \le N \le 1000$이고 $N$은 짝수이다.
• 1번부터 $N^2/2$번까지 각 번호는 정확히 두 칸에 나타나고, 그 두 칸은 변을 맞대고 있다.

첫 번째 예제에서 가장 큰 구멍의 넓이는 8이다. 3번, 6번, 7번, 8번 벽돌을 빼내면 이 구멍이 만들어진다.