题目描述

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 \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$ 的答案。

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

测试点性质

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

供题：Austin Geng