Problem: The only difference between easy and hard versions is constraints.

You are given n segments on the coordinate axis OX. Segments can intersect, lie inside each other and even coincide. The i-th segment is [l_i; r_i] (l_i ≤ r_i) and it covers all integer points j such that l_i ≤ j ≤ r_i.

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

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

Input

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

The next n lines contain segments. The i-th line contains two integers l_i and r_i (1 ≤ l_i ≤ r_i ≤ 2 ⋅ 10^5) — the endpoints of the i-th segment.

Output

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

In the second line print m distinct integers p_1, p_2, ..., p_m (1 ≤ p_i ≤ n) — indices of segments you remove in any order. If there are multiple answers, you can print any of them.

Examples

Input


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


Output


3
4 6 7 


Input


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


Output


3
1 4 5 


Input


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


Output


4
1 3 5 6 

Solution (in JAVA):

Solution:
import java.util.*;
import java.io.*;

public class Main {
    static Scanner sc = new Scanner(System.in);
    static PrintWriter out = new PrintWriter(System.out);
    static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    //    long mod = 998244353;
    long mod = (long)1e9+7;
    List<Integer>[] tree;
    int num_cycle;
    public static void main(String[] args) throws Exception {
        Main main = new Main();
//        int t = sc.nextInt();
        int t = 1;
        /*
        while(t-->0){
            main.solve();
        }*/
        for(int i=1; i<=t; i++){
            main.solve();
        }
        out.flush();
    }

    void solve(){
        int n = neInt(), k = neInt();
        int maxn = 200000+5;
        List<int[]>[] rec = new List[maxn]; // List<int[]{li, ri, i}>
        for(int i=0; i<maxn; i++){
            rec[i] = new LinkedList<>();
        }
        int[] dif = new int[maxn+5];
        for(int i=1; i<=n; i++){
            int u = neInt(), v = neInt();
            rec[u].add(new int[]{u,v,i});
        }

        int cnt = 0;
        PriorityQueue<int[]> pq = new PriorityQueue<>(n, Comparator.comparingInt(o1->-o1[1]));
        List<Integer> ans = new LinkedList<>();
        for(int i=1; i<maxn; i++){
            for(int[] cur:rec[i]){
                cnt++;
                dif[cur[1]+1]--;
                pq.add(cur);
            }
            cnt += dif[i];
            while(cnt>k){
                int[] temp = pq.poll();
                if(temp[1]<i) continue;
                cnt--;
                dif[temp[1]+1]++;
                ans.add(temp[2]);
            }
        }
        out.println(ans.size());
        for(int num:ans) out.print(num+" ");
        out.println();

    }


    String neS(){
        return sc.next();
    }
    int neInt(){
        return Integer.parseInt(sc.next());
    }
    long neLong(){
        return Long.parseLong(sc.next());
    }

    int paIn(String s){return Integer.parseInt(s);}

}