题目描述

车间里有 $n$ 个不可拆分的工件批次。每个批次都含有 $k$ 个标准件和 $1$ 个抽检件。批次 $i$ 的每个标准件硬度均为 $a_i$，抽检件硬度为 $b_i$。

你需要将所有批次排列在检验线上。设排列为 $p_1,p_2,\ldots,p_n$。对于任意 $1\le x<y\le n$，分别从批次 $p_x$ 和批次 $p_y$ 中选取一个工件；如果前一个工件的硬度严格大于后一个工件的硬度，就产生 $1$ 单位罚值。所有这样的跨批次工件对产生的罚值之和记为 $C$。硬度相等不会产生罚值，同一批次内部的工件对不计入 $C$。

请找出使 $C$ 最小的批次排列。如果有多个排列的罚值同为最小，输出编号序列字典序最小的一个。对于两个不同的编号序列，它们在第一个不同的位置上编号较小的序列字典序更小。

输入格式

从文件 inspection.in 中读取数据。

第一行输入两个整数 $n,k$，分别表示批次数和每个批次中的标准件数。

接下来 $n$ 行，第 $i$ 行输入两个整数 $a_i,b_i$，表示批次 $i$ 的标准件硬度和抽检件硬度。

输出格式

输出到文件 inspection.out 中。

输出一行 $n$ 个整数 $p_1,p_2,\ldots,p_n$，表示所求的批次排列。由于规定了字典序最小的取法，答案唯一。

样例

5 3
4 1
2 9
4 7
2 3
4 1

4 2 1 5 3

样例解释

样例 #1 中，排列 $4,2,1,5,3$ 的罚值为 $32$，不存在罚值更小的排列。批次 $1$ 和批次 $5$ 的两种硬度完全相同，把批次 $1$ 放在批次 $5$ 前面可使编号序列字典序更小。

数据规模与约定

对于所有数据，保证：

• $1\le n\le 2\times 10^5$；
• $3\le k\le 10^4$；
• $1\le a_i,b_i\le 10^9\ (1\le i\le n)$；
• $0\le C\le (k+1)^2\frac{n(n-1)}2<2.1\times 10^{18}$。

本题采用子任务捆绑计分。只有通过某个子任务内的所有测试点，才能获得该子任务的分数。各子任务独立计分。

各子任务的数据范围如下：

下发文件

下载三组测试数据，非真实测试数据