Description

有一栋 $10^9$ 层的高楼，只有 $1$ 部电梯。最初，电梯停在第 $f$ 层。

现在有 $n$ 个人在等待电梯。第 $i$ 个人现在在第 $l_i$ 层，想通过电梯前往第 $r_i$ 层（$l_i < r_i$）。由于电梯太小，每次最多只能乘坐 $1$ 个人。

每当电梯上升 $1$ 层需要耗费 $1$ 单位电能。如果电梯下降，则不耗费能量。即，从第 $x$ 层到第 $y$ 层的耗电量为 $\max(y-x, 0)$ 单位。

请你安排这 $n$ 个人乘坐电梯的顺序，使得所有人顺利到达目的地且总电能消耗最小。

更正式地，令 $a_1, a_2, \cdots, a_n$ 是 $1\sim n$ 的一个排列，表示第 $i$ 个乘坐电梯的是 $a_i$。总耗电量为

$$\sum\limits_{i = 1}^n (\max(l_{a_i} - r_{a_{(i - 1)}}, 0) + r_{a_i} - l_{a_i})$$

其中 $a_0 = 0$，$r_0 = f$（即$0$号人的终点为初始电梯位置）。

请你给出最优的搭载顺序，并输出最小的总耗电量。

需要注意，长度为 $n$ 的序列 $a_1, a_2, \cdots, a_n$ 是 $n$ 的一个排列，当且仅当 $1$ 到 $n$ 的每个整数恰好出现一次。

Input Format

输入包含多组测试数据。第一行一个整数 $T$（$1 \le T \le 10^4$），表示测试数据组数。对于每组测试数据：

第一行包含两个整数 $n$ 和 $f$（$1 \le n \le 10^5$，$1 \le f \le 10^9$），分别表示人数和初始电梯所在楼层。

接下来的 $n$ 行，每行两个整数 $l_i$ 和 $r_i$（$1 \le l_i < r_i \le 10^9$），表示第 $i$ 个人在 $l_i$ 层，希望到达 $r_i$ 层。

保证所有测试数据中 $n$ 的总和不超过 $3 \times 10^5$。

Output Format

对于每组测试数据，首先输出一行一个整数，表示最小总耗电量。接下来输出一行 $n$ 个空格分隔的整数 $a_1, a_2, \cdots, a_n$，表示乘梯顺序的最优排列。若有多个最优答案，则可输出其中任意一个。

2
4 2
3 6
1 3
2 7
5 6
2 5
2 4
6 8

11
2 1 4 3
5
2 1

Hint

由 ChatGPT 5 翻译