Problem Description

IOI Park will host $n$ events.

These events are numbered from $1$ to $n$. Event $i$ takes place from time $L_i + 10^{-1}$ to time $R_i - 10^{-1}$. It is guaranteed that $L_i$ and $R_i$ are integers.

JOI plans to attend $k$ of these events. However, JOI cannot join or leave an event in the middle. The time taken to move between event venues is negligible.

JOI prefers to attend events with smaller numbers. Specifically, if JOI attends $k$ events with numbers $a_1, \cdots, a_k$, where $1 \le a_1 < \cdots < a_k \le n$, the sequence $(a_1, \cdots, a_k)$ is considered smaller than $(b_1, \cdots, b_k)$ if there exists $j$ ( $1 \le j \le k$ ) such that for all $l$ in $[1, j-1]$, $a_l = b_l$ and $a_j < b_j$.

Given the information about each event and the number of events JOI wants to attend, determine if JOI can attend $k$ events. If possible, output the numbers of all $k$ events.

Input Format

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

The next $n$ lines each contain two positive integers $L_i$ and $R_i$.

Output Format

If JOI can attend $k$ events:
- Output $k$ lines.
- Let the numbers of the $k$ events JOI attends be $a_1, a_2, \cdots, a_k$ ( $1 \le a_1 < \cdots < a_k \le n$ ). You need to output $a_j$ on the $j$-th line ( $1 \le j \le k$ ). Ensure that the sequence $(a_1, \cdots, a_k)$ is in minimum lexicographical order.

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

Sample Input and Output

Input Sample #1

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

Output Sample #1

1
3
4
5

Input Sample #2

4 3
1 4
3 5
4 9
7 10

Output Sample #2

-1

Input Sample #3

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

Output Sample #3

1
2
4
6
7
8

Input Sample #4

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

Output Sample #4

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

Notes/Hints

Sample #1 Explanation

There are two ways to attend exactly 4 events:
- Attend events $1, 3, 4, 5$;
- Attend events $2, 3, 4, 5$.

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

Sample #2 Explanation

It is impossible to attend exactly 3 events, so output $\texttt{-1}$.

Sample #3 Explanation

This sample satisfies the conditions for all Subtasks.

Data Constraints

Due to Luogu restrictions, the first $1 \sim 20$ test points of each Subtask are not evaluated.

This problem uses a Subtask scoring method.

Note: Slashes indicate no special constraints.

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 - Competition 4 - Japanese Problem Statement.

见题面 Input 部分

见题面 Output 部分