Forklift Certified P

题目背景

checker 提供者：kjhhjki

题目描述

农夫约翰（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$ 坐标。所有箱子都有非零面积，且没有两个箱子相交。

农夫约翰计划每次从仓库的西南入口处移除一个箱子。然而，由于叉车的物理限制，他只有在没有其他箱子的任何部分位于该箱子东北角的南方和西方时，才能移除该箱子。

下面显示了一个 $N = 4$ 的示例。要移除箱子 4，阴影区域内不能有任何其他箱子。箱子 2 和 3 阻止了箱子 4 被移除，但箱子 1 不会。

帮助农夫约翰决定如何移除所有箱子！您的代码应根据整数标志 $M$ 在两种不同的模式下运行：

• 模式 1（$M = 1$）：生成一个 $1, \dots, N$ 的排列，指定一个有效的箱子移除顺序。如果存在多个有效的顺序，则输出任意一个。可以证明这样的顺序总是存在的。
• 模式 2（$M = 2$）：对于每个 $k = 1, \dots, N$，如果农夫约翰可以在箱子 $1, \dots, k-1$ 都已被移除的情况下移除箱子 $k$，则输出 1，否则输出 0。

输入格式

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

输入的第一行包含 $T$ 和 $M$。（请注意，对于每个测试用例，$M$ 都是相同的。）然后，每个测试用例的格式如下：

• 第一行包含一个整数 $N$。
• 接下来的 $N$ 行中的每一行包含四个空格分隔的整数 $x_{i1}, y_{i1}, x_{i2}, y_{i2}$：箱子 $i$ 的西南角和东北角的位置。

输出格式

对于每个测试用例：

• 如果 $M = 1$，则输出一行 $N$ 个空格分隔的整数，其中第 $j$ 个整数是要移除的第 $j$ 个箱子的标签。
• 如果 $M = 2$，则输出一行包含 $N$ 个字符的二进制字符串，指定对于每个 $k = 1, \dots, N$ 的答案。

输入输出样例 #1

输入 #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

1 3 2 4
2 3 1

输入输出样例 #2

输入 #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

输出 #2

1011
011

说明/提示

样例 1 解释

第一个测试用例对应于上面 $N = 4$ 的示例。箱子 1 没有被任何东西阻挡，箱子 3 被箱子 1 阻挡，箱子 2 被箱子 3 阻挡，而箱子 4 被箱子 2 和 3 阻挡。

样例 2 解释

第一个测试用例，箱子 2 被箱子 3 阻挡，所以农夫约翰在移除箱子 3 之前无法移除箱子 2。

测试点限制

• 测试点 3-5: $M=1$，$N\leq 1000$。
• 测试点 6: $M=2$，$N\leq 1000$。
• 测试点 7-13: $M=1$，无额外限制。
• 测试点 14-16: $M=2$，无额外限制。