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$，如果箱子 $1, \dots, k - 1$ 已经被移出，输出 $\texttt{1}$ 表示 Farmer John 可以移出箱子 $k$，否则输出 $\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$ 的答案。

样例

样例输入 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
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

说明

对于第一个测试用例，箱子 $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$，无额外限制。