题目描述

题目译自 USACO 2025 US Open Contest, Platinum Problem 1. Forklift Certified

Farmer John 正在努力成为一名合格的叉车司机！为了完成认证，他需要从一个老旧仓库中清理出 (N)（(1 \le N \le 10^5)）个箱子，这些箱子被依次编号为 (1) 到 (N)。这些箱子可以看作二维平面上的轴对齐矩形，其中 (+x) 方向朝东，(+y) 方向朝北。

箱子 (i) 的西南角坐标为 ((x_{i1}, y_{i1}))，东北角坐标为 ((x_{i2}, y_{i2}))。所有坐标都是 ([1, 2N]) 范围内的整数，且任意两个不同矩形的角不会共享相同的 (x) 或 (y) 坐标。每个箱子都有非零面积，且箱子之间互不重叠。

Farmer John 计划通过仓库的西南入口逐一移除这些箱子。然而，由于叉车的物理限制，只有当箱子东北角的南侧和西侧没有任何其他箱子部分时，他才能移除该箱子。以下是一个 (N = 4) 的例子：要移除箱子 (4)，阴影区域内不能有其他箱子；箱子 (2) 和 (3) 会阻止箱子 (4) 被移除，但箱子 (1) 不会。

请帮助 Farmer John 制定移除所有箱子的方案！你的代码需要根据一个整数标志 (M) 在两种模式下运行：

• 模式 (1)（(M = 1)）：生成一个 (1) 到 (N) 的排列，表示一个有效的箱子移除顺序。如果存在多种有效顺序，输出任意一种即可。可以证明，这样的顺序总是存在。
• 模式 (2)（(M = 2)）：对于每个 (k = 1, \dots, N)，输出 (1) 表示 Farmer John 可以在箱子 (1) 到 (k-1) 已被移除的情况下移除箱子 (k)，否则输出 (0)。

输入格式

每个输入包含 (T)（(1 \le T \le 10)）个独立的测试用例。保证所有测试用例中 (N) 的总和不超过 (5 \times 10^5)。

输入的第一行包含 (T) 和 (M)（注意：每个测试用例的 (M) 相同）。

每个测试用例的格式如下：

1. 第一行包含一个整数 (N)。
2. 接下来的 (N) 行，每行包含四个空格分隔的整数 (x_{i1}, y_{i1}, x_{i2}, y_{i2})，分别表示箱子 (i) 西南角和东北角的位置。

输出格式

对于每个测试用例：

• 如果 (M = 1)，输出一行包含 (N) 个空格分隔的整数，其中第 (j) 个整数表示第 (j) 个移除的箱子编号。
• 如果 (M = 2)，输出一行包含 (N) 个字符的二进制字符串，表示每个 (k = 1, \dots, N) 的答案。

样例 1

输入

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

说明

第一个测试用例对应上文 (N = 4) 的例子。箱子 (1) 不被任何箱子阻挡，箱子 (3) 被箱子 (1) 阻挡，箱子 (2) 被箱子 (3) 阻挡，箱子 (4) 被箱子 (2) 和 (3) 阻挡。

样例 2

输入

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

说明

对于第一个测试用例，箱子 (2) 被箱子 (3) 阻挡，因此在移除箱子 (3) 前，Farmer John 无法移除箱子 (2)。

测试点性质

• 测试点 3-5：(M=1)，(N \leq 1000)。
• 测试点 6：(M=2)，(N \leq 1000)。
• 测试点 7-13：(M=1)，没有额外限制。
• 测试点 14-16：(M=2)，没有额外限制。