Start

2019-03-02 18:00 UTC

NAIPC 2019

End

2019-03-02 23:00 UTC
The end is near!
Contest is over.
Not yet started.
Contest is starting in -256 days 12:26:32

Time elapsed

5:00:00

Time remaining

0:00:00

Problem G
Intersecting Rectangles

You are given a set of $n$ axis-aligned rectangles in a 2D plane. For this problem, two rectangles are considered to intersect if their boundaries contain any common points (in particular, two nesting rectangles don’t count as intersecting). Determine if some pair of rectangles intersect.

\includegraphics[width=1.0\textwidth ]{rectangles.jpg}

In this example, only rectangles A and B intersect.

Input

Each test case will begin with a line with a single integer $n$ ($1\! \le \! n\! \le \! 10^5$), which is the number of rectangles.

Each of the next $n$ lines will contain four space-separated integers:

$x_1$ $y_1$ $x_2$ $y_2$

($-10^9\! \le \! x_1,y_1,x_2,y_2\! \le \! 10^9, x_1\! <\! x_2, y_1\! <\! y_2$), which describe a rectangle, where $(x_1,y_1)$ is the lower left corner and $(x_2,y_2)$ is the upper right corner. All $x$ values will be distinct. All $y$ values will be distinct.

Output

Output a single integer, which is $1$ if some pair of rectangles intersect, $0$ if no pair of rectangles intersect.

Sample Input 1 Sample Output 1
3
0 0 2 2
1 1 3 4
5 7 6 8
1
Sample Input 2 Sample Output 2
4
0 0 20 20
1 1 3 4
2 10 9 12
11 3 19 18
0