{"trustable":true,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e\n .input, .output {\n border: 1px solid #888888;\n }\n .output {\n margin-bottom: 1em;\n position: relative;\n top: -1px;\n }\n .output pre, .input pre {\n background-color: #EFEFEF;\n line-height: 1.25em;\n margin: 0;\n padding: 0.25em;\n }\n \u003c/style\u003e\n \u003clink rel\u003d\"stylesheet\" href\u003d\"//codeforces.org/s/96598/css/problem-statement.css\" type\u003d\"text/css\" /\u003e\n\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027$$$$$$\u0027, right: \u0027$$$$$$\u0027, display: true},\n {left: \u0027$$$\u0027, right: \u0027$$$\u0027, display: false},\n {left: \u0027$$\u0027, right: \u0027$$\u0027, display: true},\n {left: \u0027$\u0027, right: \u0027$\u0027, display: false}\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003e\u003cspan class\u003d\"tex-font-style-it\"\u003e这个问题与前一个问题的不同之处仅在于约束条件。\u003c/span\u003e\u003c/p\u003e\u003cp\u003ePetya决定在暑假期间访问比特兰。结果发现这个国家的历史非常不寻常。\u003c/p\u003e\u003cp\u003e最初,在现在的Berland土地上有$$$n$$$个不同的国家。每个国家都有自己的领土,这在地图上被表示为一个矩形。矩形的边是与坐标轴平行的,角落位于具有整数坐标的点上。没有两个国家的领土相交,但有可能一些领土相接。随着时间的推移,有时两个国家合并成一个。只有当它们的领土的并集也是一个矩形时才会发生这种情况。最终只剩下一个国家—比特兰。\u003c/p\u003e\u003cp\u003e最初,每个国家的领土内都有一个矩形的城堡。它的边是与坐标轴平行的,角落有整数坐标。一些城堡可能与相应国家的边界、边或其他城堡相接。奇迹般的是,在所有合并之后,城堡仍然完好无损。不幸的是,他们的位置是我们恢复国家的初始领土的唯一信息。\u003c/p\u003e\u003ccenter\u003e \u003cimg class\u003d\"tex-graphics\" src\u003d\"CDN_BASE_URL/243d0e6cc2697020854cd9a8bffc45a7?v\u003d1714983940\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e 可能的比特兰形成。城堡用蓝色显示。 \u003c/center\u003e\u003cp\u003ePetya想知道为什么没有关于最初国家的信息留下。他怀疑整个故事是假的。你被推荐给他作为一个聪明的人。请检查是否存在一组可能的初始领土,可以使故事成真。\u003c/p\u003e"}},{"title":"输入","value":{"format":"HTML","content":"\u003cp\u003e第一行包含一个整数$$$n$$$($$$1 \\leq n \\leq 100\\,000$$$)— 国家和城堡的数量。\u003c/p\u003e\u003cp\u003e接下来的$$$n$$$行中,每行包含四个整数$$$a_i, b_i, c_i, d_i$$$($$$0 \\leq a_i \u0026lt; c_i \\leq 10^9$$$,$$$0 \\leq b_i \u0026lt; d_i \\leq 10^9$$$)— 第$$$i$$$座城堡的坐标,其中$$$(a_i, b_i)$$$是左下角的坐标,$$$(c_i, d_i)$$$是右上角的坐标。\u003c/p\u003e\u003cp\u003e保证没有两个城堡相交,但它们可能相接。\u003c/p\u003e"}},{"title":"输出","value":{"format":"HTML","content":"\u003cp\u003e如果存在满足故事的可能领土集合,请打印“\u003cspan class\u003d\"tex-font-style-tt\"\u003eYES\u003c/span\u003e”,否则打印“\u003cspan class\u003d\"tex-font-style-tt\"\u003eNO\u003c/span\u003e”。\u003c/p\u003e\u003cp\u003e您可以以任何大小写形式打印每个字母。\u003c/p\u003e"}},{"title":"示例","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e4\n0 0 1 2\n0 2 1 3\n1 0 2 1\n1 1 2 3\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eYES\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}},{"title":"","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e4\n0 0 2 1\n1 2 3 3\n2 0 3 2\n0 1 1 3\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003eNO\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}},{"title":"注意","value":{"format":"HTML","content":"\u003cp\u003e第一个和第二个示例中的城堡如下图所示。 \u003c/p\u003e\u003ccenter\u003e \u003cimg class\u003d\"tex-graphics\" height\u003d\"189px\" src\u003d\"CDN_BASE_URL/540e3401db8817e9b734c593ad8e9efb?v\u003d1714983940\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\" width\u003d\"189px\"\u003e \u0026nbsp; \u003cimg class\u003d\"tex-graphics\" height\u003d\"189px\" src\u003d\"CDN_BASE_URL/c221fa032370a249700fddc010b0818e?v\u003d1714983940\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\" width\u003d\"189px\"\u003e \u003c/center\u003e"}}]}