Description

There will be $n$ events in IOI Park.

These events are numbered from $1$ to $n$. Event $i$ is held from time $L_i+10^{-1}$ to time $R_i-10^{-1}$. The testdata guarantees that $L_i$ and $R_i$ are integers.

JOI wants to attend exactly $k$ events. However, JOI cannot join or leave an event in the middle. The travel time between two event venues is ignored.

JOI prefers events with smaller indices. More precisely, the indices of the $k$ events attended by JOI are $a_1,\cdots,a_k$, where $1 \le a_1 < \cdots < a_k \le n$. The sequence $(a_1, \cdots, a_k)$ is lexicographically smaller than $(b_1, \cdots, b_k)$ if and only if there exists $j\ (1 \le j \le k)$ such that for all $l$ in the interval $[1,j-1]$, we have $a_l=b_l$, and $a_j<b_j$.

Given the information of each event and the number of events $k$ that JOI will attend, determine whether JOI can attend $k$ events. If yes, output the indices of all $k$ events.

Input Format

The first line contains two positive integers $n,k$.

Lines $2$ to $n + 1$ each contain two positive integers $L_i, R_i$.

Output Format

If JOI can attend $k$ events:

• Output $k$ lines.
• Suppose the indices of the $k$ events attended by JOI are $a_1, a_2, \cdots, a_k\ (1\le a_1 < \cdots < a_k \le n）$. You need to output $a_j\ (1\le j \le k)$ on line $j$. Note that the sequence $(a_1, \cdots, a_k)$ must be the lexicographically smallest.

If JOI cannot attend $k$ events, output $\texttt{-1}$.

5 4
1 3
2 5
8 9
6 8
10 15

1
3
4
5

4 3
1 4
3 5
4 9
7 10

-1

10 6
77412002 93858605
244306432 318243514
280338037 358494212
439397354 492065507
485779890 529132783
571714810 632053254
659767854 709114867
718405631 733610573
786950301 815106357
878719468 899999649

1
2
4
6
7
8

20 16
250732298 258217736
26470443 34965880
252620676 260043105
692063405 697656580
497457675 504191511
391372149 397942668
858168758 867389085
235756850 241022021
585764751 593366541
207824318 217052204
661682908 671226688
886273261 892279963
770109416 778960597
264372562 270395107
176883483 186662376
509929119 519063796
109491630 118520141
162731982 168101507
662727316 668317158
757072772 765493222

1
2
4
5
6
7
8
9
10
11
12
13
14
15
16
17

Hint

Explanation for Sample #1

There are $2$ ways to attend exactly $4$ events.

• Attend $1, 3, 4, 5$.
• Attend $2, 3, 4, 5$.

The sequence $(1,3,4,5)$ is lexicographically smaller than $(2, 3, 4, 5)$, so output $1, 3, 4, 5$.

Explanation for Sample #2

No matter how you choose, it is impossible to attend exactly $3$ events, so output $\tt -1$.

Explanation for Sample #3

This sample satisfies the conditions of all Subtasks.

Constraints and Notes

Due to Luogu limitations, this problem will not be judged on the first $1\sim 20$ test points of each Subtask.

This problem uses Subtask scoring.

Note: a slash indicates no special restriction.

For $100\%$ of the data:

• $1\le n\le 10^5$.
• $1 \le k \le n$.
• $1\le L_i < R_i \le 10^9 (1\le i \le n)$.

Notes

This problem is translated from The 20th Japanese Olympiad in Informatics 2020/2021 Spring Training Camp - Contest 4 - Task 1 Japanese statement.

Translated by ChatGPT 5