Problem 1. Forklift Certified

USACO 2025 US Open Contest, Platinum

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, \dots, N$ 的排列，指定一个合法的箱子移除顺序。如果有多个合法的顺序，求出任意一个。可以证明这样的顺序一定存在。
• 模式 2（$M = 2$）：对于每一个 $k = 1, \dots, N$，如果 Farmer John 可以在箱子 $1, \dots, k - 1$ 已经被移除的情况下移除箱子 $k$ 则输出 $\texttt{1}$，否则输出 $\texttt{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

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

输入样例：

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$ 阻挡，所以 Farmer John 无法在移除箱子 $3$ 之前移除它。

测试点性质： 测试点 3-5：$M = 1$，$N\le 1000$。测试点 6：$M = 2$，$N \le 1000$。测试点 7-13：$M = 1$，没有额外限制。测试点 14-16：$M = 2$，没有额外限制。

供题：Austin Geng