Rating changes for the last round are temporarily rolled back. They will be returned soon. ×

174. Walls

time limit per test: 0.75 sec.
memory limit per test: 32768 KB
input: standard
output: standard

People of country T-land lived on the big plain many years ago. It is happened so that they started to quarrel, so they began to build walls to separate from each other.
One day they realized that walls surround some part of the country. Your task is to determine which wall was build first to surround a part of the T-land.

The first line of input contains one number M (1<=M<=200000) - number of walls. Each of the following M lines contains four integer numbers: Cartesian coordinates of two ends of each wall. Walls are rectilinear segments with positive length, two walls can cross only by ends, and walls can't coincide. All coordinates do not exceed 10^9 by its absolute values.

Write the answer in the single line of output. If all the walls leave the territory opened, write 0.

Sample test(s)

0 0 1 0
0 1 0 0
1 0 0 1
2 2 5 7


Author:Dmitry Orlov
Resource:Saratov ST team Spring Contest #1