목장

농부 이동호는 직사각형 모양의 목장을 여러 개 가지고 있다. 두 목장이 변의 일부를 공유하면 서로 연결되어 있다고 한다. 꼭짓점만 맞닿는 경우는 연결로 보지 않는다.

연결된 목장들의 최대 집합을 슈퍼 목장이라고 하자. 즉, 같은 슈퍼 목장에 속한 임의의 두 목장 사이에는 슈퍼 목장 밖으로 나가지 않고, 서로 연결된 목장들을 따라 이동하는 경로가 있다. 다른 목장과 연결되지 않은 목장 하나도 그 자체로 하나의 슈퍼 목장이다.

  123456789  ---------1|........62|11..223883|11..223884|11....3..5|..77..3446|99775....7|..775....

위 그림에는 모두 9개의 목장이 있고, 슈퍼 목장은 3개이다. 1번 목장은 다른 목장과 변을 공유하지 않으므로 그 자체가 하나의 슈퍼 목장이다. 2, 3, 4, 6, 8번 목장은 또 다른 슈퍼 목장을 이루고, 5, 7, 9번 목장은 나머지 슈퍼 목장을 이룬다. 1번 목장과 7번 목장은 꼭짓점만 맞닿기 때문에 연결되어 있지 않다.

슈퍼 목장의 불량도는 그 슈퍼 목장을 모두 포함하는 가장 작은 직사각형의 면적에서, 슈퍼 목장에 속한 목장들의 전체 면적을 뺀 값이다. 위 그림에서 1번 목장만 있는 슈퍼 목장의 불량도는 0이고, 2, 3, 4, 6, 8번 목장으로 이루어진 슈퍼 목장의 불량도는 10이며, 5, 7, 9번 목장으로 이루어진 슈퍼 목장의 불량도는 5이다.

이동호는 자신이 가진 목장 중 하나를 팔려고 한다. 팔 목장은 다음 규칙으로 정한다.

1. 팔 목장은 불량도가 가장 큰 슈퍼 목장에 속해야 한다. 불량도가 가장 큰 슈퍼 목장이 여러 개라면, 그중 아무 슈퍼 목장을 골라도 된다.
2. 그 목장을 팔아도, 그 목장이 속한 슈퍼 목장이 두 개 이상의 연결된 부분으로 나뉘어서는 안 된다.
3. 위 두 조건을 만족하는 목장 중 면적이 가장 작은 목장을 고른다. 그런 목장이 여러 개라면 번호가 가장 작은 목장을 고른다.

목장 정보가 주어졌을 때, 이동호가 팔 목장의 번호를 구하라.

첫째 줄에 목장의 개수 N이 주어진다. N은 5,000 이하의 자연수이다.

둘째 줄부터 N개의 줄에는 1번 목장부터 차례대로 목장 정보가 주어진다. 각 줄은 a b c d 형식이며, a는 목장의 가장 왼쪽 좌표, b는 가장 오른쪽 좌표, c는 가장 위쪽 좌표, d는 가장 아래쪽 좌표이다. 모든 좌표는 100,000 이하의 음이 아닌 정수이다.

a는 b보다 작고, c는 d보다 작다. 서로 겹치는 목장은 없다.

첫째 줄에 이동호가 팔 목장의 번호를 출력한다.