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

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.

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.

80 0 5 32 -1 5 0-3 -4 2 -1-1 -1 2 0-3 0 0 55 2 10 37 -3 10 24 -2 7 -1output
YES12232241
解題思路：
因?yàn)榫匦蔚倪厼槠鏀?shù)長(zhǎng)度 根據(jù)四色定理，染色一定會(huì)成功。
(1)我們只看左下角坐標(biāo)，如果兩個(gè)數(shù)值都為奇數(shù)，那么右上角坐標(biāo)一定兩個(gè)都為偶數(shù)，所以所有左下標(biāo)坐標(biāo)為奇數(shù)的不會(huì)相交，可賦值為1。
(2) 如果x軸為偶數(shù)，可能與1的情況左右相鄰賦值為2。
(3) 如果y軸為偶數(shù)，可能與1的情況左右相鄰，賦值為3。
(4) 其余賦值為4。
時(shí)間復(fù)雜度：O(n) 空間復(fù)雜度：O(n)
#include <iostream> #include <cstdio>#include <cstdlib>#include <cmath>#include <iomanip>#include <algorithm>#include <climits>#include <cstring>#include <string>#include <set>#include <map>#include <queue>#include <stack>#include <vector>#include <list>#define rep(i,m,n) for(int i=m;i<=n;i++)#define rsp(it,s) for(set<int>::iterator it=s.begin();it!=s.end();it++)const int inf_int = 2e9;const long long inf_ll = 2e18;#define inf_add 0x3f3f3f3f#define mod 1000000007#define pb push_back#define mp make_pair#define fi first#define se second#define pi acos(-1.0)#define pii pair<int,int>#define Lson L, mid, rt<<1#define Rson mid+1, R, rt<<1|1const int maxn=5e2+10;using namespace std;typedef  long long ll;typedef  unsigned long long  ull; inline int read(){int ra,fh;char rx;rx=getchar(),ra=0,fh=1;while((rx<'0'||rx>'9')&&rx!='-')rx=getchar();if(rx=='-')fh=-1,rx=getchar();while(rx>='0'&&rx<='9')ra*=10,ra+=rx-48,rx=getchar();return ra*fh;}//#pragma comment(linker, "/STACK:102400000,102400000")ll gcd(ll p,ll q){return q==0?p:gcd(q,p%q);}ll qpow(ll p,ll q){ll f=1;while(q){if(q&1)f=f*p;p=p*p;q>>=1;}return f;}typedef  vector<int> vi;int dir[4][2]={{1,0},{0,-1},{-1,0},{0,1}};const int N = 1e5+5;int n;int main(){    int a,b,c,d;    cin >> n;    cout << "YES"<<endl;     while(n--)    {        cin >> a>> b>>c>>d;        if(a%2&&b%2)        {            cout << 1<<endl;        }        else if(a%2==0&&b%2)        {            cout << 2<<endl;        }        else if(a%2&&b%2==0)        {            cout << 3<<endl;        }        else        {            cout << 4<<endl;        }    }    return 0;   } 膜一發(fā)dls
#include <cstdio>#include <cstring>#include <cmath>#include <algorithm>#include <vector>#include <string>#include <map>#include <set>#include <cassert>using namespace std;#define rep(i,a,n) for (int i=a;i<n;i++)#define per(i,a,n) for (int i=n-1;i>=a;i--)#define pb push_back#define mp make_pair#define all(x) (x).begin(),(x).end()#define fi first#define se second#define SZ(x) ((int)(x).size())typedef vector<int> VI;typedef long long ll;typedef pair<int,int> PII;const ll mod=1000000007;ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}// headint n,x,y;int main() {	scanf("%d",&n);	puts("YES");	rep(i,0,n) {		scanf("%d%d%*d%*d",&x,&y);		printf("%d/n",2*(x&1)+(y&1)+1);	}}