{"problem":{"name":"D. Timofey and rectangles","description":{"content":"One of Timofey's birthday presents is a colourbook in a shape of an infinite plane. On the plane _n_ rectangles with sides parallel to coordinate axes are situated. All sides of the rectangles have **","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF764D"},"statements":[{"statement_type":"Markdown","content":"One of Timofey's birthday presents is a colourbook in a shape of an infinite plane. On the plane _n_ rectangles with sides parallel to coordinate axes are situated. All sides of the rectangles have **odd** length. Rectangles cannot intersect, but they can touch each other.\n\nHelp Timofey to color his rectangles in 4 different colors in such a way that every two rectangles touching each other by side would have different color, or determine that it is impossible.\n\nTwo rectangles intersect if their intersection has positive area. Two rectangles touch by sides if there is a pair of sides such that their intersection has non-zero length\n\n<center>![image](https://espresso.codeforces.com/921f998ab26a31421f68bfe83d689852b87e52df.png) The picture corresponds to the first example</center>\n\n## Input\n\nThe first line contains single integer _n_ (1 ≤ _n_ ≤ 5·105) — the number of rectangles.\n\n_n_ lines follow. The _i_\\-th of these lines contains four integers _x_1, _y_1, _x_2 and _y_2 ( - 109 ≤ _x_1 < _x_2 ≤ 109,  - 109 ≤ _y_1 < _y_2 ≤ 109), that means that points (_x_1, _y_1) and (_x_2, _y_2) are the coordinates of two opposite corners of the _i_\\-th rectangle.\n\nIt is guaranteed, that all sides of the rectangles have **odd** lengths and rectangles don't intersect each other.\n\n## Output\n\nPrint \"_NO_\" in the only line if it is impossible to color the rectangles in 4 different colors in such a way that every two rectangles touching each other by side would have different color.\n\nOtherwise, print \"_YES_\" in the first line. Then print _n_ lines, in the _i_\\-th of them print single integer _c__i_ (1 ≤ _c__i_ ≤ 4) — the color of _i_\\-th rectangle.\n\n[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"蒂莫菲的一份生日礼物是一本形状为无限平面的彩绘书。在平面上有 #cf_span[n] 个边与坐标轴平行的矩形。所有矩形的边长均为 *奇数*。矩形之间不会相交，但可以相互接触。\n\n请帮助蒂莫菲用 #cf_span[4] 种不同的颜色为这些矩形上色，使得每两个通过边接触的矩形颜色不同；如果不可能，请指出。\n\n两个矩形若其交集面积为正，则称它们相交；两个矩形若存在一对边，其交集长度非零，则称它们通过边接触。\n\n第一行包含一个整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 5·105]）——矩形的数量。\n\n接下来 #cf_span[n] 行，第 #cf_span[i] 行包含四个整数 #cf_span[x1]、#cf_span[y1]、#cf_span[x2] 和 #cf_span[y2]（#cf_span[ - 109 ≤ x1 < x2 ≤ 109]，#cf_span[ - 109 ≤ y1 < y2 ≤ 109]），表示第 #cf_span[i] 个矩形的两个对角顶点为 #cf_span[(x1, y1)] 和 #cf_span[(x2, y2)]。\n\n保证所有矩形的边长均为 *奇数*，且矩形之间互不相交。\n\n如果无法用 #cf_span[4] 种颜色为矩形上色，使得每两个通过边接触的矩形颜色不同，请在唯一一行输出 \"_NO_\"。\n\n否则，第一行输出 \"_YES_\"，随后输出 #cf_span[n] 行，第 #cf_span[i] 行输出一个整数 #cf_span[ci]（#cf_span[1 ≤ ci ≤ 4]）——第 #cf_span[i] 个矩形的颜色。\n\n## Input\n\n第一行包含一个整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 5·105]）——矩形的数量。#cf_span[n] 行follow。第 #cf_span[i] 行包含四个整数 #cf_span[x1]、#cf_span[y1]、#cf_span[x2] 和 #cf_span[y2]（#cf_span[ - 109 ≤ x1 < x2 ≤ 109]，#cf_span[ - 109 ≤ y1 < y2 ≤ 109]），表示第 #cf_span[i] 个矩形的两个对角顶点为 #cf_span[(x1, y1)] 和 #cf_span[(x2, y2)]。保证所有矩形的边长均为 *奇数*，且矩形之间互不相交。\n\n## Output\n\n如果无法用 #cf_span[4] 种颜色为矩形上色，使得每两个通过边接触的矩形颜色不同，请在唯一一行输出 \"_NO_\"。否则，第一行输出 \"_YES_\"，随后输出 #cf_span[n] 行，第 #cf_span[i] 行输出一个整数 #cf_span[ci]（#cf_span[1 ≤ ci ≤ 4]）——第 #cf_span[i] 个矩形的颜色。\n\n[samples]","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions:**\n\n- Let $ R = \\{R_1, R_2, \\dots, R_n\\} $ be a set of $ n $ axis-aligned rectangles.\n- Each rectangle $ R_i $ is defined by its bottom-left corner $ (x_{i1}, y_{i1}) $ and top-right corner $ (x_{i2}, y_{i2}) $, with $ x_{i1} < x_{i2} $, $ y_{i1} < y_{i2} $, and all side lengths $ x_{i2} - x_{i1} $, $ y_{i2} - y_{i1} $ odd.\n- Rectangles do not intersect (intersection has zero area), but may touch along edges (intersection of sides has positive length).\n- Define adjacency: $ R_i \\sim R_j $ iff they share a side segment of positive length (i.e., their boundaries intersect in a line segment, not just a point).\n\n**Given:**\n\n- $ n \\in \\mathbb{N} $, $ 1 \\leq n \\leq 5 \\cdot 10^5 $\n- For each $ i \\in \\{1, \\dots, n\\} $, $ R_i $ has odd side lengths.\n- The adjacency graph $ G = (V, E) $, where $ V = \\{R_1, \\dots, R_n\\} $, and $ E = \\{ (R_i, R_j) \\mid R_i \\sim R_j \\} $, is planar (since rectangles are non-overlapping and axis-aligned).\n\n**Objective:**\n\nDetermine if there exists a coloring $ c: V \\to \\{1, 2, 3, 4\\} $ such that for every edge $ (R_i, R_j) \\in E $, $ c(R_i) \\ne c(R_j) $.\n\n**Key Insight:**\n\nSince all rectangles have **odd side lengths**, the coordinates of all corners are integers (as differences are odd, and assuming integer inputs), and for any rectangle $ R_i $, the center point $ \\left( \\frac{x_{i1} + x_{i2}}{2}, \\frac{y_{i1} + y_{i2}}{2} \\right) $ has **half-integer coordinates** (i.e., both coordinates are integers + 0.5).\n\nDefine a coloring function based on the parity of the floor of the center coordinates:\n\nLet:\n$$\nc(R_i) = \\left( \\left\\lfloor \\frac{x_{i1} + x_{i2}}{2} \\right\\rfloor \\bmod 2 \\right) \\cdot 2 + \\left( \\left\\lfloor \\frac{y_{i1} + y_{i2}}{2} \\right\\rfloor \\bmod 2 \\right) + 1\n$$\n\nThis maps each rectangle to one of four colors: $ \\{1, 2, 3, 4\\} $, based on the quadrant-like parity of its center.\n\n**Claim:** This coloring is always valid under the given constraints.\n\n**Justification:**\n\n- If two rectangles touch along a side, their centers must differ by at least 1 unit in the direction perpendicular to the shared side.\n- Since side lengths are odd, the centers lie at half-integers, and adjacent rectangles must be separated by an integer distance along the touching axis.\n- Thus, if two rectangles share a vertical side, their $ x $-centers differ by an integer (specifically, $ \\Delta x = \\text{integer} $), so $ \\lfloor x_{\\text{center}} \\rfloor \\bmod 2 $ differs between them.\n- Similarly, if they share a horizontal side, $ \\lfloor y_{\\text{center}} \\rfloor \\bmod 2 $ differs.\n- Therefore, the 2D parity coloring ensures adjacent rectangles differ in at least one bit of the color index → different color.\n\nHence, **a valid 4-coloring always exists** under the given constraints.\n\n**Output:**\n\n- Always print \"YES\"\n- For each rectangle $ i $, compute:\n  $$\n  c_i = 1 + 2 \\cdot \\left( \\left\\lfloor \\frac{x_{i1} + x_{i2}}{2} \\right\\rfloor \\bmod 2 \\right) + \\left( \\left\\lfloor \\frac{y_{i1} + y_{i2}}{2} \\right\\rfloor \\bmod 2 \\right)\n  $$\n\n**Formal Output:**\n\n$$\n\\boxed{\n\\begin{aligned}\n&\\text{For each rectangle } i \\text{ with corners } (x_{i1}, y_{i1}), (x_{i2}, y_{i2}): \\\\\n&\\quad \\text{Let } c_i = 1 + 2 \\cdot \\left( \\left\\lfloor \\frac{x_{i1} + x_{i2}}{2} \\right\\rfloor \\bmod 2 \\right) + \\left( \\left\\lfloor \\frac{y_{i1} + y_{i2}}{2} \\right\\rfloor \\bmod 2 \\right) \\\\\n&\\text{Output: } \\texttt{YES} \\\\\n&\\text{Output: } c_1, c_2, \\dots, c_n\n\\end{aligned}\n}\n$$","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF764D","tags":["geometry"],"sample_group":[["8\n0 0 5 3\n2 -1 5 0\n-3 -4 2 -1\n-1 -1 2 0\n-3 0 0 5\n5 2 10 3\n7 -3 10 2\n4 -2 7 -1","YES\n1\n2\n2\n3\n2\n2\n4\n1"]],"created_at":"2026-03-03 11:00:39"}}