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.
Help 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.
Two 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
<center> The picture corresponds to the first example</center>
## Input
The first line contains single integer _n_ (1 ≤ _n_ ≤ 5·105) — the number of rectangles.
_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.
It is guaranteed, that all sides of the rectangles have **odd** lengths and rectangles don't intersect each other.
## Output
Print "_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.
Otherwise, 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.
[samples]
蒂莫菲的一份生日礼物是一个形状为无限平面的彩色书。在该平面上有 #cf_span[n] 个边与坐标轴平行的矩形。所有矩形的边长均为 *奇数*。矩形之间不会相交，但可以彼此接触。
请帮助蒂莫菲用 #cf_span[4] 种不同的颜色为这些矩形着色，使得任意两个通过边接触的矩形颜色不同；若不可能实现，请指出。
两个矩形若其交集的面积为正，则称它们相交；两个矩形若存在一对边，其交集的长度非零，则称它们通过边接触。
第一行包含一个整数 #cf_span[n] (#cf_span[1 ≤ n ≤ 5·105]) —— 矩形的数量。
接下来 #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)]。
保证所有矩形的边长均为 *奇数*，且矩形之间互不相交。
如果无法用 #cf_span[4] 种颜色为矩形着色，使得任意两个通过边接触的矩形颜色不同，请在唯一一行输出 "_NO_"。
否则，第一行输出 "_YES_"，随后输出 #cf_span[n] 行，第 #cf_span[i] 行输出一个整数 #cf_span[ci] (#cf_span[1 ≤ ci ≤ 4]) —— 第 #cf_span[i] 个矩形的颜色。
## Input
第一行包含一个整数 #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)]。保证所有矩形的边长均为 *奇数*，且矩形之间互不相交。
## Output
如果无法用 #cf_span[4] 种颜色为矩形着色，使得任意两个通过边接触的矩形颜色不同，请在唯一一行输出 "_NO_"。否则，第一行输出 "_YES_"，随后输出 #cf_span[n] 行，第 #cf_span[i] 行输出一个整数 #cf_span[ci] (#cf_span[1 ≤ ci ≤ 4]) —— 第 #cf_span[i] 个矩形的颜色。
[samples]
**Definitions:**
Let $ R_i = [x_{i1}, x_{i2}] \times [y_{i1}, y_{i2}] $ for $ i = 1, 2, \dots, n $, where $ x_{i1} < x_{i2} $, $ y_{i1} < y_{i2} $, and $ x_{i2} - x_{i1} $, $ y_{i2} - y_{i1} $ are odd integers.
Rectangles are non-intersecting (intersection has zero area), but may touch along edges (intersection of sides has positive length).
Define adjacency: $ R_i \sim R_j $ if they share a side segment of positive length (i.e., their boundaries intersect in a line segment of positive measure).
**Given:**
- $ n \in \mathbb{N} $, $ 1 \leq n \leq 5 \cdot 10^5 $
- Each rectangle has sides of odd length.
- Rectangles do not intersect (only possibly touch on boundaries).
- The graph $ G = (V, E) $, where $ V = \{R_1, \dots, R_n\} $, and $ E = \{ (R_i, R_j) \mid R_i \sim R_j \} $.
**Objective:**
Determine if $ G $ is 4-colorable. If yes, output a coloring $ c: V \to \{1,2,3,4\} $ such that $ c(R_i) \ne c(R_j) $ for all $ (R_i, R_j) \in E $. Otherwise, output "NO".
**Key Observation (Structural Property):**
Because all rectangle side lengths are odd, the coordinates of all corners are integers (as differences are odd, and we can assume without loss of generality that coordinates are integers — or at least, parity is well-defined).
Define for each rectangle $ R_i $ the **parity class**:
$$
p_i = \left( \left\lfloor \frac{x_{i1}}{2} \right\rfloor \bmod 2,\ \left\lfloor \frac{y_{i1}}{2} \right\rfloor \bmod 2 \right) \in \{0,1\}^2
$$
This assigns each rectangle a 2-bit label in $ \{0,1\}^2 $, i.e., one of four classes.
**Claim:** If two rectangles touch along a side, they have different parity classes.
*Proof sketch:*
Suppose $ R_i $ and $ R_j $ touch along a vertical side. Then $ x_{i2} = x_{j1} $ (or vice versa). Since $ x_{i2} - x_{i1} $ is odd, $ x_{i1} $ and $ x_{i2} $ have opposite parity. Therefore, $ \lfloor x_{i1}/2 \rfloor \bmod 2 \ne \lfloor x_{j1}/2 \rfloor \bmod 2 $. Similarly for horizontal touches. Thus, adjacent rectangles differ in at least one coordinate of their parity class.
Hence, the mapping $ c(R_i) = p_i + 1 $ (mapping $ \{0,1\}^2 \to \{1,2,3,4\} $ bijectively) is a valid 4-coloring of the adjacency graph $ G $.
**Conclusion:**
It is always possible to color the rectangles with 4 colors under the given conditions.
**Output:**
- Print "YES"
- For each rectangle $ i $, compute:
$$
c_i = 1 + 2 \cdot \left( \left\lfloor \frac{x_{i1}}{2} \right\rfloor \bmod 2 \right) + \left( \left\lfloor \frac{y_{i1}}{2} \right\rfloor \bmod 2 \right)
$$
and output $ c_i \in \{1,2,3,4\} $.
**Formal Output:**
$$
\boxed{
\begin{array}{c}
\text{YES} \\
c_1 \\
c_2 \\
\vdots \\
c_n \\
\end{array}
}
\quad \text{where} \quad
c_i = 1 + 2 \cdot \left( \left\lfloor \frac{x_{i1}}{2} \right\rfloor \bmod 2 \right) + \left( \left\lfloor \frac{y_{i1}}{2} \right\rfloor \bmod 2 \right)
$$