Intersecting Rectangles

Time limit2sMemory limit512 MB

Summary

Given n axis-aligned rectangles with all x and y coordinates distinct, decide whether any two boundaries cross or touch. One rectangle fully containing another does not count.

Level: Hard8 of 10
Topics: Sorting, Segment tree, Simulation, Geometry
Solved: No attempts yet

Problem

You are given a set of n axis-aligned rectangles in a 2D plane. Two rectangles intersect if their boundaries contain any common points (in particular, one rectangle completely containing another does not count as intersecting). Determine whether some pair of rectangles intersect.

In this example, only rectangles A and B intersect.

Input

Each test case begins with a line containing a single integer n (1 ≤ n ≤ 105), the number of rectangles.

Each of the next n lines contains four space-separated integers:

x1 y1 x2 y2

(−109 ≤ x1, y1, x2, y2 ≤ 109, x1 < x2, y1 < y2), describing one rectangle, where (x1, y1) is the lower left corner and (x2, y2) is the upper right corner. All x values are distinct. All y values are distinct.

Output

Output a single integer: 1 if some pair of rectangles intersect, 0 if no pair of rectangles intersect.

Examples2

Example 1
Input
```
3
0 0 2 2
1 1 3 4
5 7 6 8
```
Expected output
```
1
```

Example 2

Input

Expected output