Woburn Challenge 1996

In a cubic fish tank, some fishes are swimming around. Little Billy-Bob watched the fishes move around and around until he became dizzy. At some time during the day, the fishes were all stacked together in one column, at other times they were scattered randomly in the tank and at still other times they were in an eclipsed configuration. It was this configuration that Billy-Bob enjoyed watching the most.

In this eclipsed configuration, the fishes were grouped together in vertical columns of varying length, and in each group the fishes are one on top of another. Never were there two or more groups in the same vertical column, though. Thus the tank looked like it had chains of fish hanging vertically.

Little Billy-Bob would try to figure out which level (or depth) in the tank had the most number of fishes when it was in this configuration. But he had to do it fast before the fishes moved past one another and ruined all his fun.

You can help Billy-Bob by writing a program that does the work for him. The fish tank will be an $n\times n\times n$ cube and hence in the eclipsed configuration it will have at most $n^2$ groups as it has only $n^2$ separate vertical columns. You are to find the level (or depth) at which there is the largest number of fishes. The top level of the tank is level 1, and the bottom level of the tank is level $n$. If multiple levels each have the most number of fish, give the topmost of these levels.

For example, consider a $3\times 3\times 3$ cube with a group of 3 fish on the center vertical column, and two single fish on opposite corners. If we label the columns with co-ordinates from $(1,1)$ to $(3,3)$ this could be described as:

• In column $(2,2)$: A stack of fish from level 1 to level 3
• In column $(1,1)$: A stack of fish from level 1 to level 1 (i.e. only in level 1)
• In column $(3,3)$: A stack of fish from level 3 to level 3 (i.e. only in level 3)

In this case, there are two fish each at levels 1 and 3, so we give the topmost (1).

Input Specification

In the data file, there are 5 data sets. The first line of each data set is $n$ $(1\le n\le 50)$, the size of the cubic fishtank to be considered. The next lines each contain four integers $(x,y,t,b)$ which indicate a column of fish at $(x,y)$ whose top fish is in level $t$ and whose bottom fish is in level $b$. (And of course, there are fish at each level $t+1,t+2,\dots ,b$ since Billy only likes these particular fish-stack configurations as mentioned above). This set of fish-columns is terminated by a line containing all zeroes.

Output Specification

Give the topmost level of all those containing the biggest number of fish.

Sample Input

3
1 1 3 3
2 2 1 3
3 3 1 1
0 0 0 0

(and 4 more data sets)

Sample Output

1