#include <bits/stdc++.h>
using namespace std;
const long long MAXN = 2e5 + 7;
vector<long long> tree(4 * MAXN), add(4 * MAXN);
void push(long long v, long long tl, long long tr) {
  tree[v] += add[v] * (tr - tl);
  if (tl + 1 != tr) {
    add[v * 2] += add[v];
    add[v * 2 + 1] += add[v];
  }
  add[v] = 0;
}
long long get(long long v, long long tl, long long tr, long long l,
              long long r) {
  push(v, tl, tr);
  if (l >= tr || tl >= r)
    return 0;
  else if (l <= tl && r >= tr)
    return tree[v];
  else {
    long long tm = (tl + tr) / 2;
    auto kek = get(v * 2, tl, tm, l, r);
    auto lol = get(v * 2 + 1, tm, tr, l, r);
    return kek + lol;
  }
}
void upd(long long v, long long tl, long long tr, long long l, long long r,
         long long delta) {
  push(v, tl, tr);
  if (l >= tr || tl >= r)
    return;
  else if (l <= tl && r >= tr) {
    add[v] += delta;
    push(v, tl, tr);
  } else {
    long long tm = (tl + tr) / 2;
    upd(v * 2, tl, tm, l, r, delta);
    upd(v * 2 + 1, tm, tr, l, r, delta);
    tree[v] = tree[v * 2] + tree[v * 2 + 1];
  }
}
int32_t main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  long long n, k;
  cin >> n >> k;
  vector<pair<long long, long long> > num(n);
  vector<long long> used(207);
  vector<vector<long long> > events;
  for (long long i = 0; i < n; i++) {
    long long l, r;
    cin >> l >> r;
    num[i].first = l;
    num[i].second = r;
    upd(1, 0, MAXN, l, r + 1, 1);
    events.push_back({l, 0, l, r, i});
    events.push_back({r, 2, l, r, i});
  }
  for (long long i = 1; i < MAXN; i++) events.push_back({i, 1, -1, -1, -1});
  sort(events.begin(), events.end());
  vector<long long> kek(n), ans;
  multiset<vector<long long> > all;
  for (long long i = 0; i < (long long)events.size(); i++) {
    vector<long long> ev = events[i];
    long long type = ev[1];
    if (type == 0) {
      all.insert({-ev[3], -ev[2], ev[4]});
    } else if (type == 2) {
      if (all.find({-ev[3], -ev[2], ev[4]}) != all.end())
        all.erase(all.find({-ev[3], -ev[2], ev[4]}));
    } else {
      long long point = ev[0];
      long long smth = get(1, 0, MAXN, point, point + 1);
      while (smth > k) {
        auto kek = *all.begin();
        long long l = -kek[1], r = -kek[0], pos = kek[2];
        upd(1, 0, MAXN, l, r + 1, -1);
        all.erase(all.begin());
        ans.push_back(pos + 1);
        smth--;
      }
    }
  }
  cout << (long long)ans.size() << "\n";
  for (auto el : ans) cout << el << " ";
  cout << "\n";
  return 0;
}

### Prompt

In cpp, your task is to solve the following 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 

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
const long long MAXN = 2e5 + 7;
vector<long long> tree(4 * MAXN), add(4 * MAXN);
void push(long long v, long long tl, long long tr) {
  tree[v] += add[v] * (tr - tl);
  if (tl + 1 != tr) {
    add[v * 2] += add[v];
    add[v * 2 + 1] += add[v];
  }
  add[v] = 0;
}
long long get(long long v, long long tl, long long tr, long long l,
              long long r) {
  push(v, tl, tr);
  if (l >= tr || tl >= r)
    return 0;
  else if (l <= tl && r >= tr)
    return tree[v];
  else {
    long long tm = (tl + tr) / 2;
    auto kek = get(v * 2, tl, tm, l, r);
    auto lol = get(v * 2 + 1, tm, tr, l, r);
    return kek + lol;
  }
}
void upd(long long v, long long tl, long long tr, long long l, long long r,
         long long delta) {
  push(v, tl, tr);
  if (l >= tr || tl >= r)
    return;
  else if (l <= tl && r >= tr) {
    add[v] += delta;
    push(v, tl, tr);
  } else {
    long long tm = (tl + tr) / 2;
    upd(v * 2, tl, tm, l, r, delta);
    upd(v * 2 + 1, tm, tr, l, r, delta);
    tree[v] = tree[v * 2] + tree[v * 2 + 1];
  }
}
int32_t main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  long long n, k;
  cin >> n >> k;
  vector<pair<long long, long long> > num(n);
  vector<long long> used(207);
  vector<vector<long long> > events;
  for (long long i = 0; i < n; i++) {
    long long l, r;
    cin >> l >> r;
    num[i].first = l;
    num[i].second = r;
    upd(1, 0, MAXN, l, r + 1, 1);
    events.push_back({l, 0, l, r, i});
    events.push_back({r, 2, l, r, i});
  }
  for (long long i = 1; i < MAXN; i++) events.push_back({i, 1, -1, -1, -1});
  sort(events.begin(), events.end());
  vector<long long> kek(n), ans;
  multiset<vector<long long> > all;
  for (long long i = 0; i < (long long)events.size(); i++) {
    vector<long long> ev = events[i];
    long long type = ev[1];
    if (type == 0) {
      all.insert({-ev[3], -ev[2], ev[4]});
    } else if (type == 2) {
      if (all.find({-ev[3], -ev[2], ev[4]}) != all.end())
        all.erase(all.find({-ev[3], -ev[2], ev[4]}));
    } else {
      long long point = ev[0];
      long long smth = get(1, 0, MAXN, point, point + 1);
      while (smth > k) {
        auto kek = *all.begin();
        long long l = -kek[1], r = -kek[0], pos = kek[2];
        upd(1, 0, MAXN, l, r + 1, -1);
        all.erase(all.begin());
        ans.push_back(pos + 1);
        smth--;
      }
    }
  }
  cout << (long long)ans.size() << "\n";
  for (auto el : ans) cout << el << " ";
  cout << "\n";
  return 0;
}

```