Trong một nhà máy kẹo có một cỗ máy bí ẩn. Máy có một dãy cửa ra được đánh số từ \(1\) đến \(n\); mỗi viên kẹo rơi ra ngay khi được làm xong. Trước mỗi phiên sản xuất, máy in danh sách cho biết thời điểm và cửa ra của từng viên kẹo.

Chủ nhà máy có thể lắp các xe tự động chạy phía dưới dãy cửa để hứng kẹo. Không viên kẹo nào được phép rơi xuống sàn, nhưng vì vận hành xe rất tốn kém nên cần dùng ít xe nhất có thể. Mỗi xe chạy với vận tốc một khoảng cách giữa hai cửa trong một giây. Trước khi phiên sản xuất bắt đầu, mỗi xe có thể được đặt sẵn tại cửa nơi nó sẽ hứng viên kẹo đầu tiên.

Hãy tìm số xe ít nhất cần dùng và chỉ ra xe nào hứng từng viên kẹo.

Dữ liệu vào

Dòng đầu chứa số nguyên \(n\), số viên kẹo trong phiên sản xuất. Mỗi dòng trong \(n\) dòng tiếp theo chứa hai số nguyên \(s_i,t_i\): cửa ra và thời điểm của viên kẹo thứ \(i\). Các cặp \((s_i,t_i)\) đôi một khác nhau.

Dữ liệu ra

Dòng đầu chứa số nguyên \(w\), số xe ít nhất cần dùng. Các xe được đánh số từ \(1\) đến \(w\).

Mỗi dòng trong \(n\) dòng tiếp theo chứa ba số nguyên \(s_j,t_j,w(j)\), cho biết xe \(w(j)\) sẽ ở cửa \(s_j\) tại thời điểm \(t_j\) để hứng viên kẹo đó. Mỗi cặp cửa–thời điểm trong dữ liệu vào phải xuất hiện đúng một lần; các dòng có thể được in theo thứ tự bất kỳ.

Nếu có nhiều phương án, bạn có thể in ra bất kỳ phương án nào.

Ràng buộc

Phân nhóm

• 20% số điểm: \(n\le 85\) và số xe tối ưu \(w\le 4\).
• 60% số điểm: \(n\le 8\,000\).

Ví dụ

5
1 1
2 3
1 5
3 4
2 6

2
1 1 1
2 3 1
1 5 2
3 4 1
2 6 2