题目描述

小 X 和小 J 是公园的管理员，他们负责一条名为“彩虹小径”的直路。这条路总长度为 $10^9$，位置可以用一个实数 $x \in [0, 10^9)$ 表示。

为了美化环境，他们决定招募 $N$ 名志愿者（编号为 $1$ 到 $N$）为小径铺设彩色地砖。在筹备会上，每位志愿者被分配了一段连续的路段 $[L_i, R_i)$，即所有满足 $L_i \leq x < R_i$ 的位置。编号越大的志愿者需要承担更长的路段，因此路段长度随编号增加而不减：对于所有 $1 \leq i < j \leq n$，有 $R_i - L_i \leq R_j - L_j$。

铺设工作分 $N$ 轮进行。每轮选择一名尚未工作的志愿者，让他负责铺设自己路段内尚未被铺过的部分（即之前其他志愿者已经铺过的位置不必再铺）。为了公平，每一轮都选择本次将铺设新路段长度最小的志愿者；若有多个，则选择编号最小的。

小 J 负责安排顺序，小 X 负责记录。请你帮助小 J 确定这 $n$ 名志愿者的工作顺序。

输入格式

第一行两个整数 $T,tid$，表示有 $T$ 组测试数据，测试点编号为 $tid$ （样例 $tid=0$）。

对于每组测试数据：

第一行一个整数 $n$。接下来的 $n$ 行每行包含两个整数 $L_i$ 和 $R_i$。

所有区间互不相同，即对于所有 $1 \leq i < j \leq n$，有 $(L_i, R_i) \neq (L_j, R_j)$。

输出格式

对于每组测试数据，输出一行 $n$ 个整数，表示工作顺序。第 $i$ 个整数表示在第 $i$ 轮工作的志愿者编号。

输入输出样例

输入 #1

1 0
6
1 2
2 3
3 4
4 5
1 3
3 5

输出 #1

1 2 5 3 4 6

输入 #2

1 0
4
3 7
10 14
1 6
6 11

输出 #2

1 3 2 4

数据范围

对于 100% 的数据，满足 $1 \leq n \leq 2.5 \times 10^5$，$1 \leq \sum n \leq 5 \times 10^5$，$1 \leq L_i < R_i \leq 10^9$。

对于 $1 \leq i < j \leq n$，满足 $R_i - L_i \leq R_j - L_j$。

特殊性质 $A$：对于任意 $i \neq j$，不存在 $L_i < L_j$ 且 $R_i > R_j$ 的情况。

特殊性质 $B$：任意两个区间要么存在包含关系，要么不交。