#include <bits/stdc++.h>
using namespace std;
void input(int n, int a[]) {
  for (int i = 0; i < n; ++i) cin >> a[i];
}
long long bin_expo(long long A, long long B, long long M) {
  long long res = 1LL;
  while (B > 0) {
    if (B % 2 == 1) {
      res = (res * A) % M;
    }
    A = (A * A) % M;
    B = B / 2;
  }
  return res;
}
vector<pair<pair<int, int>, int> > v;
int k, n;
pair<int, int> seg[1000000];
void build(int node, int l, int r) {
  if (l == r) {
    seg[node] = make_pair(v[l].first.second, l);
    return;
  }
  int mid = (l + r) >> 1;
  build(2 * node, l, mid);
  build(2 * node + 1, mid + 1, r);
  seg[node] = max(seg[2 * node], seg[2 * node + 1]);
}
void update(int node, int l, int r, int idx) {
  if (l == r && l == idx) {
    seg[node] = make_pair(INT_MIN, idx);
    return;
  }
  int mid = (l + r) >> 1;
  if (idx <= mid)
    update(2 * node, l, mid, idx);
  else
    update(2 * node + 1, mid + 1, r, idx);
  seg[node] = max(seg[2 * node], seg[2 * node + 1]);
}
pair<int, int> query(int node, int l, int r, int ql, int qr) {
  if (l > r || l > qr || r < ql) return make_pair(0, 0);
  if (ql <= l && qr >= r) {
    return seg[node];
  }
  int mid = (l + r) >> 1;
  pair<int, int> p1 = query(2 * node, l, mid, ql, qr);
  pair<int, int> p2 = query(2 * node + 1, mid + 1, r, ql, qr);
  return max(p1, p2);
}
int main() {
  cin >> n >> k;
  int a[300000] = {0};
  int rr = 0;
  for (int i = 0; i < n; i++) {
    int x, y;
    cin >> x >> y;
    rr = max(rr, y);
    v.push_back(make_pair(make_pair(x, y), i));
    a[x]++;
    a[y + 1]--;
  }
  sort(v.begin(), v.end());
  build(1, 0, n - 1);
  for (int i = 0; i < 300000; i++) {
    a[i] += a[i - 1];
  }
  int b[300000] = {0};
  vector<int> ans;
  for (int i = 0; i < rr + 2; i++) {
    b[i] += b[i - 1];
    if ((a[i] - b[i]) <= k)
      continue;
    else {
      while ((a[i] - b[i]) > k) {
        int idx =
            upper_bound(v.begin(), v.end(), make_pair(make_pair(i + 1, 0), 0)) -
            v.begin();
        idx--;
        b[i]++;
        pair<int, int> pq = query(1, 0, n - 1, 0, idx);
        b[v[pq.second].first.second + 1]--;
        ans.push_back(v[pq.second].second);
        update(1, 0, n - 1, pq.second);
      }
    }
  }
  int c[300000] = {0};
  for (int i = 0; i < n; i++) {
    int f = 0;
    for (int j = 0; j < ans.size(); j++)
      if (ans[j] == v[i].second) f = 1;
    if (f == 0) {
      c[v[i].first.first]++;
      c[v[i].first.second + 1]--;
    }
  }
  cout << ans.size() << endl;
  for (int i = 0; i < ans.size(); i++) cout << ans[i] + 1 << " ";
  cout << endl;
  return 0;
}

### Prompt

Develop a solution in cpp to the problem described below:

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 

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
void input(int n, int a[]) {
  for (int i = 0; i < n; ++i) cin >> a[i];
}
long long bin_expo(long long A, long long B, long long M) {
  long long res = 1LL;
  while (B > 0) {
    if (B % 2 == 1) {
      res = (res * A) % M;
    }
    A = (A * A) % M;
    B = B / 2;
  }
  return res;
}
vector<pair<pair<int, int>, int> > v;
int k, n;
pair<int, int> seg[1000000];
void build(int node, int l, int r) {
  if (l == r) {
    seg[node] = make_pair(v[l].first.second, l);
    return;
  }
  int mid = (l + r) >> 1;
  build(2 * node, l, mid);
  build(2 * node + 1, mid + 1, r);
  seg[node] = max(seg[2 * node], seg[2 * node + 1]);
}
void update(int node, int l, int r, int idx) {
  if (l == r && l == idx) {
    seg[node] = make_pair(INT_MIN, idx);
    return;
  }
  int mid = (l + r) >> 1;
  if (idx <= mid)
    update(2 * node, l, mid, idx);
  else
    update(2 * node + 1, mid + 1, r, idx);
  seg[node] = max(seg[2 * node], seg[2 * node + 1]);
}
pair<int, int> query(int node, int l, int r, int ql, int qr) {
  if (l > r || l > qr || r < ql) return make_pair(0, 0);
  if (ql <= l && qr >= r) {
    return seg[node];
  }
  int mid = (l + r) >> 1;
  pair<int, int> p1 = query(2 * node, l, mid, ql, qr);
  pair<int, int> p2 = query(2 * node + 1, mid + 1, r, ql, qr);
  return max(p1, p2);
}
int main() {
  cin >> n >> k;
  int a[300000] = {0};
  int rr = 0;
  for (int i = 0; i < n; i++) {
    int x, y;
    cin >> x >> y;
    rr = max(rr, y);
    v.push_back(make_pair(make_pair(x, y), i));
    a[x]++;
    a[y + 1]--;
  }
  sort(v.begin(), v.end());
  build(1, 0, n - 1);
  for (int i = 0; i < 300000; i++) {
    a[i] += a[i - 1];
  }
  int b[300000] = {0};
  vector<int> ans;
  for (int i = 0; i < rr + 2; i++) {
    b[i] += b[i - 1];
    if ((a[i] - b[i]) <= k)
      continue;
    else {
      while ((a[i] - b[i]) > k) {
        int idx =
            upper_bound(v.begin(), v.end(), make_pair(make_pair(i + 1, 0), 0)) -
            v.begin();
        idx--;
        b[i]++;
        pair<int, int> pq = query(1, 0, n - 1, 0, idx);
        b[v[pq.second].first.second + 1]--;
        ans.push_back(v[pq.second].second);
        update(1, 0, n - 1, pq.second);
      }
    }
  }
  int c[300000] = {0};
  for (int i = 0; i < n; i++) {
    int f = 0;
    for (int j = 0; j < ans.size(); j++)
      if (ans[j] == v[i].second) f = 1;
    if (f == 0) {
      c[v[i].first.first]++;
      c[v[i].first.second + 1]--;
    }
  }
  cout << ans.size() << endl;
  for (int i = 0; i < ans.size(); i++) cout << ans[i] + 1 << " ";
  cout << endl;
  return 0;
}

```