题干：

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 4different 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

题目大意：

    一个无限大的平面被分为无数个小正方形格子，一些相连的格子们可以组成矩形。给出左下角和右上角的坐标来表示该矩形（比如给出 0 0 5 3 即代表坐标为（0,0）开始到（5,3）之间的所有格子组成的矩形）。矩形的长和宽只能是奇数，给出一些矩形的坐标表示，要求写程序为所有的矩形染色，相邻的矩形不可染同种颜色（题中已经给出所有的矩形没有两两相交的情况出现，且相邻的条件为存在大于0长度的公共边），如果存在染色方案则输出YES并且输出N个矩形的每种染色情况（如果存在多种情况输出任意一种即可），如果不存在染色方案则输出NO结束。

解题报告：

思路描述：　由于我们已知任意一个地图都4可着色，因此第一行一定永远是"YES"。关于着色方案，我们重点关注所有的边均为奇数的条件。

由于所有的边均为奇数，那么对于两个相邻的矩形，我们考虑其左下角的坐标：设其为A (x1,y1)和B (x2,y2);

　　当A与B水平相邻时，即如下图所示（黄色为A，蓝绿色为B，其中(x1,y1)以及(x2,y2)分别表示红色的点和蓝色的点）：

　　我们可以看出对于任意两个相邻的矩形，其必有(x1与x2)或(y1与y2)的奇偶性不一致（因为所有矩形边长均为奇数），由于我们有4种染色方案（设为1 2 3 4），因此我们可以构造其染色情况为

[(x%2+2*(y%2))+4]%4+1（其中x和y表示该矩形左下角坐标），即可保证相邻的矩形中没有同色的情况（因为该染色情况下同色当且仅当x与y的奇偶性一致）。

AC代码：

#include<iostream>
#include<cmath>
using namespace std;
int main() {
	int n, a, b, c, d;
	ios::sync_with_stdio(false);
	cin >> n;
	cout <<"YES"<<endl;
	while(n--) {
		cin>>a>>b>>c>>d;
		int tmp = abs(a) % 2 + 2 * (abs(b) % 2);
		cout << tmp + 1 << endl;
	}
	return 0;
}

总结：

[(x%2+2*(y%2))+4]%4+1这个公式也可以，这两种构造的方式虽然结果不同但是都符合题意。注意负数取模问题！