題目連接:http://codeforces.com/PRoblemset/problem/763/B

——————————————————————————————-. time limit per test2 seconds memory limit per test256 megabytes

inputstandard input outputstandard output

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

The picture corresponds to the first example 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 x1, y1, x2 and y2 (?-?109?≤?x1?<?x2?≤?109, ?-?109?≤?y1?<?y2?≤?109), that means that points (x1,?y1) and (x2,?y2) 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 ci (1?≤?ci?≤?4) — the color of i-th rectangle.

Example

input

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

output

YES 1 2 2 3 2 2 4 1

——————————————————————————————-. 題目大意: 就是在一個二維平面上有n個矩形,現在讓你給這n個矩形4種涂色之一,使得相鄰的矩形顏色不同. (矩形的兩條邊都是整數) 解題思路:

我這種智障是做不出來的,本來并不想寫題解,但是無意中看了Tutorial中的discuss發現一個特別容易理解的.

We may assume that our rectangles are drawn on an infinite sheet of squared paper. Divide it into squares 2 × 2 and mark the cells in each square by 1, 2, 3, 4 clockwise starting from the upper left corner. Since both sides of each rectangle are of odd length, its corner cells are marked by the same number. Let us number four different colors by 1, 2, 3, 4 and paint each rectangle with the color whose number marks the corner cells. It is readily seen that the numbers in the corners of any two adjacent rectangles are distinct. 我們可能會認為我們的矩形被畫在無限平方的紙。將紙分成一個個2×2方塊,然后從左上角順時針方向開始標上1,2,3,4(代表顏色)。由于每個矩形的兩邊都是奇數長度，所以它的所有格子標記為相同的數。讓我們用1，2，3，4個不同的顏色編號，并繪制每個矩形的顏色的數字標記的格子。很容易看出，任何兩個相鄰矩形的角的數是不同的。 (基本是機翻……可以自己畫一畫就容易理解了,Orz)

附本題代碼 ——————————————————————————————-.