21793번 - Event Hopping 2 서브태스크다국어

In IOI Park, N events will be held soon. The events are numbered from 1 to N. The i-th event (1 ≤ i ≤ N) will start at time L_i + 0.1 and finish at time R_i − 0.1. Here L_i and R_i are integers.

JOI-kun will attend exactly K events among them. It is forbidden to enter an event after it starts, or to leave an event before it finishes. We ignore the time to move between the locations of events.

JOI-kun wants to attend events with small indices. More precisely, let a₁, . . . , a_K (1 ≤ a₁ < · · · < a_K ≤ N) be the indices of the events JOI-kun will attend. Then (a₁, . . . , a_K) should be the smallest possible sequence in lexicographic order. Here, a sequence (a₁, . . . , a_K) is smaller than another sequence (b₁, . . . , b_K) in lexicographic order iff there exists j (1 ≤ j ≤ K) satisfying both “a_ℓ = b_ℓ for every 1 ≤ ℓ ≤ j − 1” and “a_j < b_j.”

Write a program which, given the information of the events and the number K of events JOI-kun will attend, determines whether JOI-kun will be able to attend K events or not. If it is possible for JOI-kun to attend K events, the program should calculate the K events JOI-kun will attend.

Read the following data from the standard input. Given values are all integers.

N K
L1 R1
.
.
.
LN RN

If JOI-kun will not be able to attend K events, output one line containing -1 to the standard output.

If JOI-kun will be able to attend K events, output K lines to the standard output. Let a₁, . . . , a_K (1 ≤ a₁ < · · · < a_K ≤ N) be the indices of the events JOI-kun will attend. The j-th line (1 ≤ j ≤ K) of output should contain a_j. Here (a₁, . . . , a_K) should be the smallest possible sequence in lexicographic order.

• 1 ≤ N ≤ 100 000.
• 1 ≤ K ≤ N.
• 1 ≤ L_i < R_i ≤ 1 000 000 000 (1 ≤ i ≤ N).