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:
// package Quarantine;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;
import java.util.TreeSet;

public class TooManySegments {
    public static void update(int tree[],int lazy[],int s,int e,int l,int r,int val,int node){
//        System.out.println(s+" "+e);
        if(lazy[node]!=0){
            tree[node]+=lazy[node];
            if(s!=e){
                lazy[2*node]+=lazy[node];
                lazy[2*node+1]+=lazy[node];
            }
            lazy[node]=0;
        }
        if(s>r||e<l){
            return;
        }
        if(s>=l&&e<=r){
            tree[node]+=val;
            if(s!=e){
                lazy[2*node]+=val;
                lazy[2*node+1]+=val;
            }
            return;
        }
        int mid=(s+e)/2;
        update(tree,lazy,s,mid,l,r,val,2*node);
        update(tree,lazy,mid+1,e,l,r,val,2*node+1);
        tree[node]=tree[2*node]+tree[2*node+1];
    }
    public static int query(int tree[],int lazy[],int s,int e,int ind,int node){
        if(lazy[node]!=0){
            tree[node]+=lazy[node];
            if(s!=e){
                lazy[2*node]+=lazy[node];
                lazy[2*node+1]+=lazy[node];
            }
            lazy[node]=0;
        }
        if(s==e){
            return tree[node];
        }
        int mid=(s+e)/2;
        if(ind<=mid){
            return query(tree,lazy,s,mid,ind,2*node);
        }
        else{
            return query(tree,lazy,mid+1,e,ind,2*node+1);
        }
    }
    public static void main(String[] args)throws IOException {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st=new StringTokenizer(br.readLine());
        int n=Integer.parseInt(st.nextToken());
        int k=Integer.parseInt(st.nextToken());
        ArrayList<Segment> seggments=new ArrayList<>();
        int lim=200000;
        int tree[]=new int[4*lim+4];
        int lazy[]=new int[4*lim+4];
        for(int i=1;i<=n;i++){
            st=new StringTokenizer(br.readLine());
            int l=Integer.parseInt(st.nextToken());
            int r=Integer.parseInt(st.nextToken());
            update(tree,lazy,1,200000,l,r,1,1);
            seggments.add(new Segment(l,r,i));
        }
        Collections.sort(seggments);
        int j=0;
        TreeSet<LenInfo> set=new TreeSet<>();
        ArrayList<Integer> ans=new ArrayList<>();
        TreeSet<Right> rights=new TreeSet<>();
        ArrayList<LenInfo> copylen=new ArrayList<>();
        ArrayList<Right> copyright=new ArrayList<>();
        for(int i=0;i<n;i++){
            Segment curr=seggments.get(i);
            copylen.add(new LenInfo(i,curr.r));
            copyright.add(new Right(i,curr.r));
        }
        for(int i=1;i<=200000;i++){
            int q=query(tree,lazy,1,200000,i,1);
            while(j<n){
                Segment curr=seggments.get(j);
                if(curr.l<=i&&curr.r>=i){
                    set.add(new LenInfo(j,curr.r));
                    rights.add(new Right(j,curr.r));
                    j++;
                }
                else{
                    break;
                }
            }
            ArrayList<Integer> remove=new ArrayList<>();
            for(Right right:rights){
                if(right.r<i){
                    remove.add(right.index);
                }
                else{
                    break;
                }
            }
            for(int ind:remove){
                rights.remove(copyright.get(ind));
                set.remove(copylen.get(ind));
            }
            remove=new ArrayList<>();
            if(q>k){
                for(LenInfo lenInfo:set){
                    remove.add(lenInfo.index);
                    Segment curr=seggments.get(lenInfo.index);
                    ans.add(curr.index);
                    update(tree,lazy,1,200000,curr.l,curr.r,-1,1);
                    q--;
                    if(q==k){
                        break;
                    }
                }
                for(int ind:remove){
                    rights.remove(copyright.get(ind));
                    set.remove(copylen.get(ind));
                }
            }
        }
        System.out.println(ans.size());
        StringBuilder print=new StringBuilder();
        for(int i=0;i<ans.size();i++){
            print.append(ans.get(i)+" ");
        }
        System.out.println(print.toString());
    }
}

class Segment implements Comparable<Segment>{
    int l,r,index;
    public Segment(int l,int r,int index){
        this.l=l;
        this.r=r;
        this.index=index;
    }

    @Override
    public int compareTo(Segment o) {
        if(this.l!=o.l){
            return this.l-o.l;
        }
        else{
            return this.r-o.r;
        }
    }
}

class LenInfo implements Comparable<LenInfo>{
    int index,len;
    public LenInfo(int index,int len){
        this.index=index;
        this.len=len;
    }

    @Override
    public int compareTo(LenInfo o) {
        if(this.index==o.index){
            return 0;
        }
        if(this.len<o.len){
            return 1;
        }
        else{
            return -1;
        }
    }

    @Override
    public String toString() {
        return this.index+" "+this.len;
    }
}

class Right implements Comparable<Right>{
    int index,r;
    public Right(int index,int r){
        this.index=index;
        this.r=r;
    }

    @Override
    public int compareTo(Right o) {
        if(this.index==o.index){
            return 0;
        }
        if(this.r<o.r){
            return -1;
        }
        else{
            return 1;
        }
    }

    @Override
    public String toString() {
        return this.index+" "+this.r;
    }
}