Lexicographically Smallest Non‐Overlapping Event Selection

IOI Park will host \(n\) events, numbered from \(1\) to \(n\). Event \(i\) takes place from \(L_i+10^{-1}\) to \(R_i-10^{-1}\), where \(L_i\) and \(R_i\) are integers. JOI wants to participate in exactly \(k\) events. However, he must attend each event from start to finish and cannot join in the middle or leave early. Note that the travel time between events is negligible.

JOI prefers events with smaller indices. More precisely, if the events he chooses are \(a_1, a_2, \dots, a_k\) satisfying \(1 \le a_1 < a_2 < \dots < a_k \le n\), then among all valid selections the sequence \((a_1,\dots,a_k)\) should be lexicographically smallest. The lexicographical order is defined in the usual way: \((a_1,\dots,a_k)\) is smaller than \((b_1,\dots,b_k)\) if there exists an index \(j\) with \(1 \le j \le k\) such that \(a_1=b_1, \dots, a_{j-1}=b_{j-1}\) and \(a_j < b_j\).

In order for JOI to attend two consecutive events \(i\) and \(j\) (with \(i < j\)) without any scheduling conflicts, the entire duration of event \(i\) must finish before event \(j\) starts. Since event \(i\) runs from \(L_i+10^{-1}\) to \(R_i-10^{-1}\) and event \(j\) runs from \(L_j+10^{-1}\) to \(R_j-10^{-1}\), the non-overlap condition is:

[ R_i - 0.1 \le L_j + 0.1 \quad\Longleftrightarrow\quad R_i \le L_j + 0.2. ]

Because \(L_j\) and \(R_i\) are integers, the inequality \(R_i \le L_j + 0.2\) holds if and only if \(R_i \le L_j\). Thus, for two events to be attended consecutively, we require \(R_{a_\ell} \le L_{a_{\ell+1}}\) for all \(1 \le \ell < k\).

Given the event times and the number \(k\) of events that JOI wants to attend, determine if there exists a valid selection of \(k\) events. If so, output the lexicographically smallest sequence of event indices that satisfies the conditions; otherwise, output -1.

inputFormat

The first line contains two integers \(n\) and \(k\) (the number of events and the number of events JOI wants to attend). Each of the next \(n\) lines contains two integers \(L_i\) and \(R_i\) (\(1 \leq i \leq n\)) representing the start and end integers of event \(i\).

You may assume that \(L_i\) and \(R_i\) are such that the event takes place from \(L_i+0.1\) to \(R_i-0.1\) and that \(1 \le n \le 10^5\) and \(1 \le k \le n\) (constraints may vary).

outputFormat

If a valid selection exists, output the \(k\) event indices in increasing order separated by spaces on a single line. If no valid selection exists, output -1.

sample

3 2
1 3
3 5
4 6

1 2