На летние каникулы Петя приехал в Байтландию. Как оказалась, история этого государства весьма необычна.
Изначально, до появления Байтландии, на её территории были расположены n различных стран. Каждое государство владело своей территорией, которую можно было представить на карте как прямоугольник, стороны которого параллельны осям координат, а вершины расположены в целочисленных точках. Никакие две страны не пересекались, однако они могли касаться сторонами. Иногда в результате агрессивных переговоров и мирных военных походов две страны объединялись в одну. Слияние происходило только в том случае, если после объединения их владений снова получалась прямоугольная территория. В конце концов осталось только одно государство — Байтландия.
В начале времён территория каждой страны содержала внутри себя ровно один прямоугольный замок, где стороны этого замка параллельны осям координат, а вершины расположены в целочисленных точках. Допускается, что границы замка могли прилегать к границе соответствующей территории страны и к границам других замков. Удивительным образом, даже после всех переворотов, замки прекрасно сохранились. Но, к сожалению, это единственная информация, которая позволяет хоть как-то судить об изначальном расположении стран.
Возможное формирование Байтландии. Замки отмечены синим цветом.
Петя не смог смириться с тем, что не осталось никаких данных об изначальных странах. У него возникло подозрение, что вся эта история всего лишь вымысел. Он знает, что вы умный человек, и поэтому просит у вас помощи. Требуется выяснить, существует ли расположение изначальных государств, для которых может быть верна данная история, или нет.
Входные данные
Первая строка содержит одно целое число n (1 ≤ n ≤ 100000) — количество замков и стран.
Каждая из следующих n строк содержат четыре целых числа a
i, b
i, c
i, d
i (0 ≤ a
i < c
i ≤ 10
9, 0 ≤ b
i < d
i ≤ 10
9) — координаты вершин i-го замка, где (a
i, b
i) — координаты левой нижней точки, а (c
i, d
i) — правой верхней.
Гарантируется, что никакие два замка не пересекаются, однако они могут касаться сторонами.
Выходные данные
Если существуют расположения изначальных стран, для которых верна данная история, то выведите « YES », иначе выведите « NO ».
Примечание
На картинках ниже изображено расположение замков в первом и втором примере.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
4
0 0 1 2
0 2 1 3
1 0 2 1
1 1 2 3 |
YES |
| 2 |
4
0 0 2 1
1 2 3 3
2 0 3 2
0 1 1 3 |
NO |