Tô màu hình chữ nhật bằng 4 màu

Trên mặt phẳng tọa độ vô hạn có $n$ hình chữ nhật với các cạnh song song với các trục tọa độ. Tất cả các cạnh của các hình chữ nhật đều có độ dài lẻ. Các hình chữ nhật không cắt nhau (phần giao có diện tích bằng $0$), nhưng có thể chạm nhau qua cạnh.

Hai hình chữ nhật được gọi là chạm nhau qua cạnh nếu tồn tại một cặp cạnh (một của hình thứ nhất, một của hình thứ hai) sao cho phần giao của hai cạnh đó có độ dài lớn hơn $0$.

Hãy tô màu $n$ hình chữ nhật bằng $4$ màu sao cho hai hình chữ nhật bất kỳ chạm nhau qua cạnh phải mang màu khác nhau, hoặc thông báo rằng việc tô màu là không thể.

Dữ liệu vào

• Dòng đầu tiên chứa số nguyên $n$ — số hình chữ nhật.
• $n$ dòng tiếp theo, dòng thứ $i$ chứa bốn số nguyên $x_1,y_1,x_2,y_2$ — tọa độ hai đỉnh đối diện của hình chữ nhật thứ $i$.

Dữ liệu ra

• Nếu không thể tô màu hợp lệ, in ra một dòng duy nhất chứa NO.
• Ngược lại, in ra YES ở dòng đầu, sau đó $n$ dòng, dòng thứ $i$ chứa một số nguyên $c_i$ ($1\le c_i\le 4$) — màu của hình chữ nhật thứ $i$.

Ràng buộc

• $1\le n\le 5·{10}^5$
• $-{10}^9\le x_1<x_2\le {10}^9$, $-{10}^9\le y_1<y_2\le {10}^9$
• $x_2-x_1$ và $y_2-y_1$ đều lẻ.
• Các hình chữ nhật không cắt nhau (phần giao có diện tích bằng $0$).

Ví dụ