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 implements Comparable<Node>{
			public int l;
			public int r;
			public int idx;
			public int count;
			Node(int n,int m,int i) {
		    l = n;
		    r = m;
		    idx=i;
		    count=1;
			}
			@Override
			public int compareTo(Node o) {
				// TODO Auto-generated method stub
				if(o.idx==this.idx) {
					return 0;
				}
				if(this.r<o.r) {
					return 1;
				}
				if(this.r==o.r) {
					if(this.idx<o.idx) {
						return -1;
					}
					return 1;
				}
				return -1;
				
			}
			@Override
			public int hashCode() {
			    return idx;
			}
			
		}
 
	
	
	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;
        		ArrayList<Node>[] a=new ArrayList[max];
        		ArrayList<Node>[] b=new ArrayList[max];
        		for(int i=0;i<max;i++) {
        			a[i]=new ArrayList<Node>();
        			b[i]=new ArrayList<Node>();
        		}
        		for(int i=0;i<n;i++) {
        			int x=in.nextInt();
        			int y=in.nextInt();
        			Node cur=new Node(x,y,i+1);
        			a[x].add(cur);
        			b[y].add(cur);
        		}
        		SortedSet<Node> set=new TreeSet<>();
        		HashSet<Integer> res=new HashSet<Integer>();
        		for(int i=1;i<=200000;i++) {
        			for(Node j:a[i]) {
        				set.add(j);
        			}
        			while(set.size()>k) {
        				Node v=set.first();
        				res.add(v.idx);
        				set.remove(v);
        			}
        			for(Node j:b[i]) {
        				if(set.contains(j)) {
        					set.remove(j);
        				}
        				
        			}
        		}
        		Iterator<Integer> itr=res.iterator();
        		out.println(res.size());
        		while(itr.hasNext()) {
        			out.print(itr.next()+" ");
        		}
        		out.println();
 
        	}
        }
 
    }
 
    
    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];         
    }
    
    
}