Tại công viên IOI sắp diễn ra \(N\) sự kiện, được đánh số từ \(1\) đến \(N\). Sự kiện thứ \(i\) bắt đầu vào thời điểm \(L_i+0.1\) và kết thúc vào thời điểm \(R_i-0.1\), trong đó \(L_i\) và \(R_i\) là các số nguyên.

JOI-kun muốn tham dự đúng \(K\) sự kiện. Cậu không được đến sau khi một sự kiện bắt đầu hoặc rời đi trước khi sự kiện đó kết thúc. Bỏ qua thời gian di chuyển giữa các địa điểm tổ chức sự kiện.

JOI-kun muốn ưu tiên những sự kiện có chỉ số nhỏ. Cụ thể, gọi \(a_1,\ldots,a_K\) là các chỉ số sự kiện được chọn, được sắp xếp sao cho \(1\le a_1<\cdots<a_K\le N\). Cậu muốn dãy \((a_1,\ldots,a_K)\) nhỏ nhất có thể theo thứ tự từ điển.

Dãy \((a_1,\ldots,a_K)\) nhỏ hơn dãy \((b_1,\ldots,b_K)\) theo thứ tự từ điển khi và chỉ khi tồn tại \(j\) (\(1\le j\le K\)) sao cho \(a_\ell=b_\ell\) với mọi \(1\le\ell<j\) và \(a_j<b_j\).

Cho thông tin về các sự kiện và số \(K\), hãy xác định JOI-kun có thể tham dự đúng \(K\) sự kiện hay không. Nếu có, hãy tìm các sự kiện cậu cần chọn theo yêu cầu trên.

Dữ liệu vào

Đọc từ đầu vào chuẩn theo dạng:

N K
L_1 R_1
...
L_N R_N

Mọi giá trị đầu vào đều là số nguyên.

Dữ liệu ra

Nếu không thể tham dự đúng \(K\) sự kiện, xuất một dòng chứa -1.

Nếu có thể, xuất \(K\) dòng. Dòng thứ \(j\) chứa \(a_j\), với \(1\le a_1<\cdots<a_K\le N\), sao cho dãy chỉ số này nhỏ nhất theo thứ tự từ điển trong tất cả các cách chọn hợp lệ.

Ràng buộc

• \(1\le N\le 100\,000\).
• \(1\le K\le N\).
• \(1\le L_i<R_i\le 1\,000\,000\,000\) với mọi \(1\le i\le N\).

Phân nhóm

1. \(7\) điểm: \(L_i\le L_{i+1}\) với mọi \(1\le i\le N-1\).
2. \(1\) điểm: \(N\le 20\).
3. \(31\) điểm: \(N\le 3000\).
4. \(61\) điểm: Không có ràng buộc bổ sung.

Ví dụ

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

Nguồn

JOI 2020/2021, Spring Training Camp, Contest 4. Tác giả: 髙谷悠太. Bản Việt hóa từ đề chính thức của Ủy ban Olympic Tin học Nhật Bản, theo CC BY-SA 4.0.