这个问题与下一个问题的区别仅在于约束。
Petya 决定在暑假期间参观 Byteland。原来,这个国家的历史颇不寻常。
最初,现在伯兰的土地上有 $$$n$$$ 个不同的国家。每个国家都有自己的领土,在地图上用矩形表示。矩形的边与轴平行,角位于具有整数坐标的点处。两个国家的领土没有相交,但有些领土可能相互接触。随着时间的推移,有时两个国家会合并为一个国家。只有当他们的领土联合起来也是一个矩形时才会发生这种情况。最终只剩下一个国家——拜特兰。
最初,每个国家在其领土内都有一座长方形的城堡。它的边平行于轴,它的角有整数坐标。有些城堡可能会触及相应国家和侧面或其他城堡的边界。奇迹般的是,在所有的联合之后,城堡仍然完好无损。不幸的是,他们的位置是我们恢复这些国家最初领土的唯一信息。
Byteland 的可能形成。城堡以蓝色显示。
Petya 想知道为什么没有关于最初国家的信息。他怀疑整个故事都是假的。你被推荐给他作为一个聪明人。请检查是否存在一组可能的初始领土可以使故事成真。
输入
第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 1000$$$) — 国家和城堡的数量。
接下来的 $$$n$$$ 行包含四个整数 $$$a_i, b_i, c_i, d_i$$$ ($$$0 \leq a_i < c_i \leq 10^9$$$, $$$0 \leq b_i < d_i \leq 10^9$$$) - 的坐标$$$i$$$-th 城堡,其中 $$$(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
输出 #1
YES
输入 #2
4 0 0 2 1 1 2 3 3 2 0 3 2 0 1 1 3
输出 #2
NO
注意
第一个和第二个示例中的城堡如下图所示。