#P1249D2. Too Many Segments (hard version)

    ID: 2077 Type: RemoteJudge 2000ms 256MiB Tried: 0 Accepted: 0 Difficulty: (None) Uploaded By: Tags>data structuresgreedysortings*1800

Too Many Segments (hard version)

No submission language available for this problem.

Description

The only difference between easy and hard versions is constraints.

You are given nn segments on the coordinate axis OXOX. Segments can intersect, lie inside each other and even coincide. The ii-th segment is [li;ri][l_i; r_i] (liril_i \le r_i) and it covers all integer points jj such that lijril_i \le j \le r_i.

The integer point is called bad if it is covered by strictly more than kk segments.

Your task is to remove the minimum number of segments so that there are no bad points at all.

The first line of the input contains two integers nn and kk (1kn21051 \le k \le n \le 2 \cdot 10^5) — the number of segments and the maximum number of segments by which each integer point can be covered.

The next nn lines contain segments. The ii-th line contains two integers lil_i and rir_i (1liri21051 \le l_i \le r_i \le 2 \cdot 10^5) — the endpoints of the ii-th segment.

In the first line print one integer mm (0mn0 \le m \le n) — the minimum number of segments you need to remove so that there are no bad points.

In the second line print mm distinct integers p1,p2,,pmp_1, p_2, \dots, p_m (1pin1 \le p_i \le n) — indices of segments you remove in any order. If there are multiple answers, you can print any of them.

Input

The first line of the input contains two integers nn and kk (1kn21051 \le k \le n \le 2 \cdot 10^5) — the number of segments and the maximum number of segments by which each integer point can be covered.

The next nn lines contain segments. The ii-th line contains two integers lil_i and rir_i (1liri21051 \le l_i \le r_i \le 2 \cdot 10^5) — the endpoints of the ii-th segment.

Output

In the first line print one integer mm (0mn0 \le m \le n) — the minimum number of segments you need to remove so that there are no bad points.

In the second line print mm distinct integers p1,p2,,pmp_1, p_2, \dots, p_m (1pin1 \le p_i \le n) — indices of segments you remove in any order. If there are multiple answers, you can print any of them.

Samples

Sample Input 1

7 2
11 11
9 11
7 8
8 9
7 8
9 11
7 9

Sample Output 1

3
4 6 7

Sample Input 2

5 1
29 30
30 30
29 29
28 30
30 30

Sample Output 2

3
1 4 5

Sample Input 3

6 1
2 3
3 3
2 3
2 2
2 3
2 3

Sample Output 3

4
1 3 5 6