Codeforces Round #395 (Div. 1) B. Timofey and rectangles

N 個の長方形が与えられる。長方形の四隅は格子点上にあり、辺は軸に平行、辺の長さは奇数である。長方形同士は重ならない。

長方形を 4 色で塗り分けたい。ただし接している長方形の色は異なる必要がある。このような塗り分け方が存在するなら、その一例を示せ。

かならず構成可能できる。これは平面グラフが四彩色可能である（四色定理）ことからすぐに分かる。しかし、実際にその彩色方法を見つけるのは容易ではない。
ではどうやって構成すれば良いのだろうか。

実は、長方形の左上の座標を (x,y) としたとき、(x%2)×2+(y%2)+1 で塗ればいい。(x,y)と接している長方形は、x 座標か y 座標のパリティがずれるからである。