Farmer John đang luyện tập để được cấp chứng chỉ lái xe nâng! Trong quá trình huấn luyện, ông cần dọn \(N\) (\(1\le N\le 10^5\)) thùng hàng, được đánh số thuận tiện từ \(1\) đến \(N\), ra khỏi một nhà kho cũ.

Các thùng hàng có thể được mô hình hóa thành những hình chữ nhật song song với các trục trong mặt phẳng hai chiều, trong đó hướng \(+x\) là hướng đông và hướng \(+y\) là hướng bắc. Thùng \(i\) có góc tây nam tại \((x_{i1},y_{i1})\) và góc đông bắc tại \((x_{i2},y_{i2})\). Mọi tọa độ đều là số nguyên trong đoạn \([1,2N]\), và không có hai góc thuộc hai hình chữ nhật khác nhau có cùng tọa độ \(x\) hoặc cùng tọa độ \(y\). Mọi thùng đều có diện tích khác không và không có hai thùng nào giao nhau.

Farmer John dự định lần lượt đưa từng thùng ra ngoài qua lối vào phía tây nam của nhà kho. Tuy nhiên, do giới hạn vật lý của xe nâng, ông chỉ có thể đưa một thùng ra nếu không có phần nào của bất kỳ thùng nào khác vừa nằm về phía nam vừa nằm về phía tây so với góc đông bắc của thùng đó.

Ví dụ với \(N=4\) được minh họa dưới đây. Để đưa thùng \(4\) ra, vùng tô đậm không được chứa bất kỳ thùng nào khác. Thùng \(2\) và \(3\) cản thùng \(4\), còn thùng \(1\) thì không.

Hãy giúp Farmer John quyết định cách đưa tất cả các thùng ra ngoài! Chương trình của bạn phải hoạt động ở hai chế độ riêng biệt, được xác định bởi cờ nguyên \(M\):

• Chế độ 1 (\(M=1\)): Sinh một hoán vị của \(1,\dots,N\) mô tả một thứ tự dỡ thùng hợp lệ. Nếu có nhiều thứ tự hợp lệ, hãy tìm bất kỳ thứ tự nào. Có thể chứng minh rằng luôn tồn tại một thứ tự như vậy.
• Chế độ 2 (\(M=2\)): Với mỗi \(k=1,\dots,N\), in \(\texttt{1}\) nếu Farmer John có thể đưa thùng \(k\) ra sau khi các thùng \(1,\dots,k-1\) đã được đưa ra, và in \(\texttt{0}\) nếu không thể.

Dữ liệu vào

Mỗi dữ liệu vào gồm \(T\) (\(1\le T\le 10\)) bộ dữ liệu độc lập. Đảm bảo tổng tất cả các giá trị \(N\) trong một dữ liệu vào không vượt quá \(5\cdot 10^5\).

Dòng đầu tiên chứa \(T\) và \(M\). (Lưu ý rằng \(M\) giống nhau cho mọi bộ dữ liệu.) Sau đó mỗi bộ dữ liệu có định dạng như sau:

• Dòng đầu tiên chứa một số nguyên \(N\).
• Mỗi dòng trong \(N\) dòng tiếp theo chứa bốn số nguyên cách nhau bởi dấu cách \(x_{i1},y_{i1},x_{i2},y_{i2}\), là vị trí góc tây nam và góc đông bắc của thùng \(i\).

Dữ liệu ra

Với mỗi bộ dữ liệu:

• Nếu \(M=1\), in một dòng gồm \(N\) số nguyên cách nhau bởi dấu cách, trong đó số nguyên thứ \(j\) là nhãn của thùng thứ \(j\) cần đưa ra.
• Nếu \(M=2\), in một dòng gồm một xâu nhị phân dài \(N\) ký tự, mô tả đáp án cho mỗi \(k=1,\dots,N\).

Ví dụ

2 1
4
1 6 2 8
6 2 7 3
3 1 4 7
5 4 8 5
3
1 5 3 6
4 1 5 2
2 3 6 4

1 3 2 4
2 3 1

2 2
4
1 6 2 8
6 2 7 3
3 1 4 7
5 4 8 5
3
1 5 3 6
4 1 5 2
2 3 6 4

1011
011

Phân nhóm

• Dữ liệu 3–5: \(M=1\), \(N\le 1000\).
• Dữ liệu 6: \(M=2\), \(N\le 1000\).
• Dữ liệu 7–13: \(M=1\), không có ràng buộc bổ sung.
• Dữ liệu 14–16: \(M=2\), không có ràng buộc bổ sung.

Đề bài: Austin Geng.

Nguồn

USACO 2025 US Open Contest, Platinum — Forklift Certified: https://usaco.org/index.php?page=viewproblem2&cpid=1524