Pastures

Farmer Dongho owns several rectangular pastures. Two pastures are connected if they share part of a side. Pastures that only touch at a corner are not connected.

A super pasture is a maximal set of connected pastures. In other words, for any two pastures in the same super pasture, there is a path from one to the other that stays inside the super pasture by moving through connected pastures. A pasture that is not connected to any other pasture is also a super pasture by itself.

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

The diagram above contains 9 pastures and 3 super pastures. Pasture 1 shares no side with any other pasture, so it is a super pasture by itself. Pastures 2, 3, 4, 6, and 8 form another super pasture, and pastures 5, 7, and 9 form the remaining one. Pastures 1 and 7 only touch at a corner, so they are not connected.

The badness of a super pasture is the area of the smallest rectangle containing the entire super pasture minus the total area of the pastures inside it. In the diagram, the super pasture containing only pasture 1 has badness 0, the super pasture containing pastures 2, 3, 4, 6, and 8 has badness 10, and the remaining super pasture has badness 5.

Dongho wants to sell one of his pastures. He chooses it by the following rules.

1. The pasture must belong to a super pasture with the maximum badness. If several super pastures have that maximum badness, he may choose any one of them.
2. Selling the pasture must not split its super pasture into two or more connected parts.
3. Among the pastures satisfying the first two rules, he chooses one with the smallest area. If there are several such pastures, he chooses the one with the smallest number.

Given the pasture information, determine the number of the pasture Dongho will sell.

The first line contains the number of pastures N. N is a positive integer not greater than 5,000.

Each of the next N lines describes one pasture, in order from pasture 1 to pasture N. A line has the form a b c d, where a is the leftmost coordinate, b is the rightmost coordinate, c is the top coordinate, and d is the bottom coordinate of the pasture. All coordinates are non-negative integers not greater than 100,000.

a is less than b, c is less than d, and no two pastures overlap.

Print the number of the pasture Dongho will sell on the first line.