Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

The problem statement has recently been changed. View the changes.

×
D. New Year and Conference

time limit per test

2 secondsmemory limit per test

1024 megabytesinput

standard inputoutput

standard outputFilled with optimism, Hyunuk will host a conference about how great this new year will be!

The conference will have $$$n$$$ lectures. Hyunuk has two candidate venues $$$a$$$ and $$$b$$$. For each of the $$$n$$$ lectures, the speaker specified two time intervals $$$[sa_i, ea_i]$$$ ($$$sa_i \le ea_i$$$) and $$$[sb_i, eb_i]$$$ ($$$sb_i \le eb_i$$$). If the conference is situated in venue $$$a$$$, the lecture will be held from $$$sa_i$$$ to $$$ea_i$$$, and if the conference is situated in venue $$$b$$$, the lecture will be held from $$$sb_i$$$ to $$$eb_i$$$. Hyunuk will choose one of these venues and all lectures will be held at that venue.

Two lectures are said to overlap if they share any point in time in common. Formally, a lecture held in interval $$$[x, y]$$$ overlaps with a lecture held in interval $$$[u, v]$$$ if and only if $$$\max(x, u) \le \min(y, v)$$$.

We say that a participant can attend a subset $$$s$$$ of the lectures if the lectures in $$$s$$$ do not pairwise overlap (i.e. no two lectures overlap). Note that the possibility of attending may depend on whether Hyunuk selected venue $$$a$$$ or venue $$$b$$$ to hold the conference.

A subset of lectures $$$s$$$ is said to be venue-sensitive if, for one of the venues, the participant can attend $$$s$$$, but for the other venue, the participant cannot attend $$$s$$$.

A venue-sensitive set is problematic for a participant who is interested in attending the lectures in $$$s$$$ because the participant cannot be sure whether the lecture times will overlap. Hyunuk will be happy if and only if there are no venue-sensitive sets. Determine whether Hyunuk will be happy.

Input

The first line contains an integer $$$n$$$ ($$$1 \le n \le 100\,000$$$), the number of lectures held in the conference.

Each of the next $$$n$$$ lines contains four integers $$$sa_i$$$, $$$ea_i$$$, $$$sb_i$$$, $$$eb_i$$$ ($$$1 \le sa_i, ea_i, sb_i, eb_i \le 10^9$$$, $$$sa_i \le ea_i, sb_i \le eb_i$$$).

Output

Print "YES" if Hyunuk will be happy. Print "NO" otherwise.

You can print each letter in any case (upper or lower).

Examples

Input

2 1 2 3 6 3 4 7 8

Output

YES

Input

3 1 3 2 4 4 5 6 7 3 4 5 5

Output

NO

Input

6 1 5 2 9 2 4 5 8 3 6 7 11 7 10 12 16 8 11 13 17 9 12 14 18

Output

YES

Note

In second example, lecture set $$$\{1, 3\}$$$ is venue-sensitive. Because participant can't attend this lectures in venue $$$a$$$, but can attend in venue $$$b$$$.

In first and third example, venue-sensitive set does not exist.

Codeforces (c) Copyright 2010-2022 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: May/22/2022 13:26:03 (g1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|