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.io.OutputStream;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.*;
import java.io.BufferedReader;
import java.io.InputStreamReader;
//import java.math.*;
 
/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
 
public class Main {
	static class Node {
		  public int l;
		  public int r;
		  public int idx;

		  Node(int n,int m,int i) {
		    l = n;
		    r = m;
		    idx=i;
		  }
		}

	
	
	static int MD= 1000000007;
    public static void main(String[] args) throws IOException {
    	OutputStream outputStream = System.out;
        InputReader in = new InputReader();
        PrintWriter out = new PrintWriter(outputStream);
        TaskC solver = new TaskC();
        solver.solve(1, in, out);
        out.close();
    }
 
    static class TaskC {
    
        public void solve(int testNumber, InputReader in, PrintWriter out) throws IOException {
        	
        	int t=1;
        	while(t-->0) {
        		int n=in.nextInt();
        		int k=in.nextInt();
        		int max=2000001;
        		int[] cnt=new int[max];
        		Node[] a=new Node[n];
        		for(int i=0;i<n;i++) {
        			int x=in.nextInt();
        			int y=in.nextInt();
        			a[i]=new Node(x,y,i+1);
        		}
        		nsort(a,0,n);
        		PriorityQueue<Node> pq=new PriorityQueue<Node>(new comp());
        		HashSet<Integer> res=new HashSet<Integer>();
        		int cur=0;
        		int s=0;
        		for(int i=1;i<max;i++) {
        			while(cur<n && a[cur].l<=i) {
        				pq.add(a[cur]);
        				cnt[a[cur].r+1]--;
        				cur++;
        				s++;
        			}
        			s+=cnt[i];
        			while(s>k) {
        				Node v=pq.poll();
        				res.add(v.idx);
        				s--;
        				cnt[v.r+1]++;
        			}
        		}
        		Iterator<Integer> itr=res.iterator();
        		out.println(res.size());
        		while(itr.hasNext()) {
        			out.println(itr.next());
        		}

        	}
        }

    }
    static class comp implements Comparator<Node>{
    	public int compare(Node n1, Node n2) {
    		if(n1.r>n2.r) {
    			return -1;
    		}
    		else {
    			return 1;
    		}
    	}
    }
  
    
    static class InputReader
    {
        BufferedReader br;
        StringTokenizer st;
 
        public InputReader()
        {
            br = new BufferedReader(new
                     InputStreamReader(System.in));
        }
 
        String next()
        {
            while (st == null || !st.hasMoreElements())
            {
                try
                {
                    st = new StringTokenizer(br.readLine());
                }
                catch (IOException  e)
                {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }
   
        int nextInt()
        {
            return Integer.parseInt(next());
        }
 
        long nextLong()
        {
            return Long.parseLong(next());
        }
 
        double nextDouble()
        {
            return Double.parseDouble(next());
        }
 
        String nextLine()
        {
            String str = "";
            try
            {
                str = br.readLine();
            }
            catch (IOException e)
            {
                e.printStackTrace();
            }
            return str;
        }
    
    }
    static void sort(int[] a, int low, int high) 
    {
        int N = high - low;         
        if (N <= 1) 
            return; 
        int mid = low + N/2; 
        sort(a, low, mid); 
        sort(a, mid, high); 
        int[] temp = new int[N];
        int i = low, j = mid;
        for (int k = 0; k < N; k++) 
        {
            if (i == mid)  
                temp[k] = a[j++];
            else if (j == high) 
                temp[k] = a[i++];
            else if (a[j]<a[i]) 
                temp[k] = a[j++];
            else 
                temp[k] = a[i++];
        }    
        for (int k = 0; k < N; k++) 
            a[low + k] = temp[k];         
    }
    public static long fexp(long x, long y, long p) {
        long res = 1;      
        
       
        x = x % p;  
      
        while (y > 0) 
        { 
         
            if((y & 1)==1) 
                res = (res * x) % p; 
      
          
            y = y >> 1;  
            x = (x * x) % p;  
        } 
        return res; 
        
    }
    static int gcd(int a, int b) 
    { 
        if (b == 0) 
            return a; 
        return gcd(b, a % b);  
          
    }
    public static void nsort(Node[] a, int low, int high) 
    {
        int N = high - low;         
        if (N <= 1) 
            return; 
        int mid = low + N/2; 
        // recursively sort 
        nsort(a, low, mid); 
        nsort(a, mid, high); 
        // merge two sorted subarrays
        Node[] temp = new Node[N];
        int i = low, j = mid;
       
        for (int k = 0; k < N; k++) 
        {
            if (i == mid)  
                temp[k] = a[j++];
            else if (j == high) 
                temp[k] = a[i++];
            else if (a[j].l<a[i].l) 
                temp[k] = a[j++];
            else 
                temp[k] = a[i++];
        }   
        for (int k = 0; k < N; k++) 
            a[low + k] = temp[k];         
    }
    
    
}