← 返回题目列表

Codeforces · 763/B

B. Timofey 和矩形

中文机器翻译题面 查看原题

Timofey 的生日礼物之一是一本无限平面形状的彩色书。平面上有 n 个边长与坐标轴平行的矩形。矩形的所有边的长度均为奇数。矩形不能相交,但可以互相接触。

帮助 Timofey 用 4 种不同的颜色为他的矩形着色,使得每两个并排接触的矩形都会有不同的颜色,或者确定这是不可能的。

如果两个矩形的交集面积为正,则它们相交。如果有一对边且它们的交集具有非零长度,则两个矩形边接触

该图对应第一个例子

输入

第一行包含单个整数 n (1 ≤ n ≤ 5·105) — 矩形的数量。

n 行如下。其中第 i 行包含四个整数 x1、y1、x2 和 y2(- 109 ≤ x1 < x2 ≤ 109,- 109 ≤ y1 < y2 ≤ 109),这意味着点 (x1, y1) 和 (x2, y2) 是第 i 个矩形的两个对角的坐标。

保证矩形的所有边都具有奇数长度并且矩形不相互相交。

输出

如果不可能用 4 种不同的颜色为矩形着色,使得每两个并排接触的矩形具有不同的颜色,则在唯一的行中打印“NO”。

否则,在第一行打印“YES”。然后打印 n 行,其中第 i 行打印单个整数 ci (1 ≤ ci ≤ 4) – 第 i 个矩形的颜色。

示例

输入 #1

8
0 0 5 3
2 -1 5 0
-3 -4 2 -1
-1 -1 2 0
-3 0 0 5
5 2 10 3
7 -3 10 2
4 -2 7 -1

输出 #1

YES
1
2
2
3
2
2
4
1