#include <bits/stdc++.h>
using namespace std;
const long long INF = 0x3f3f3f3f;
const long long MOD = 998244353;
const long long N = 6e5 + 10;
struct SEG {
  struct Node {
    long long l, r, mx, idx, cg;
  } t[N << 2];
  void build(long long p, long long l, long long r) {
    t[p].l = l, t[p].r = r;
    t[p].mx = 0, t[p].cg = t[p].idx = -1;
    if (l == r) {
      return;
    }
    long long mid = (l + r) >> 1;
    build((p << 1), l, mid);
    build((p << 1 | 1), mid + 1, r);
  }
  void calc(long long p, long long x, long long id) {
    t[p].mx = t[p].cg = x;
    t[p].idx = id;
  }
  void pushdown(long long p) {
    if (t[p].cg != -1) {
      calc((p << 1), t[p].cg, t[p].idx);
      calc((p << 1 | 1), t[p].cg, t[p].idx);
      t[p].cg = -1;
    }
  }
  void pushup(long long p) {
    t[p].mx = max(t[(p << 1)].mx, t[(p << 1 | 1)].mx);
    t[p].idx = (t[(p << 1)].mx >= t[(p << 1 | 1)].mx) ? t[(p << 1)].idx
                                                      : t[(p << 1 | 1)].idx;
  }
  void update(long long p, long long l, long long r, long long x,
              long long id) {
    if (t[p].l > r || t[p].r < l) return;
    if (t[p].l >= l && t[p].r <= r) {
      calc(p, x, id);
      return;
    }
    pushdown(p);
    update((p << 1), l, r, x, id);
    update((p << 1 | 1), l, r, x, id);
    pushup(p);
  }
  pair<long long, long long> query(long long p, long long l, long long r) {
    if (t[p].l > r || t[p].r < l) return make_pair(0, -1);
    if (t[p].l >= l && t[p].r <= r) {
      return make_pair(t[p].mx, t[p].idx);
    }
    pushdown(p);
    pair<long long, long long> L = query((p << 1), l, r),
                               R = query((p << 1 | 1), l, r);
    return (L.first >= R.first) ? L : R;
  }
} seg;
signed main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  long long n, m;
  cin >> n >> m;
  vector<long long> hsh, pre(n, -1);
  vector<vector<pair<long long, long long> > > a(n);
  for (long long i = 0; i < m; i++) {
    long long id, l, r;
    cin >> id >> l >> r;
    a[id - 1].push_back({l, r});
    hsh.push_back(l);
    hsh.push_back(r);
  }
  sort(hsh.begin(), hsh.end());
  hsh.resize(unique(hsh.begin(), hsh.end()) - hsh.begin());
  seg.build(1, 0, hsh.size() - 1);
  for (long long i = 0; i < n; i++) {
    long long mx = 0, prt = -1;
    for (auto &j : a[i]) {
      j.first = lower_bound(hsh.begin(), hsh.end(), j.first) - hsh.begin();
      j.second = lower_bound(hsh.begin(), hsh.end(), j.second) - hsh.begin();
      pair<long long, long long> tmp = seg.query(1, j.first, j.second);
      if (tmp.first > mx) {
        mx = tmp.first;
        prt = tmp.second;
      }
    }
    pre[i] = prt;
    for (auto j : a[i]) {
      seg.update(1, j.first, j.second, mx + 1, i);
    }
  }
  cout << n - seg.t[1].mx << '\n';
  vector<long long> vis(n);
  for (long long i = seg.t[1].idx; i >= 0; i = pre[i]) {
    vis[i] = 1;
  }
  for (long long i = 0; i < n; i++) {
    if (!vis[i]) {
      cout << i + 1 << ' ';
    }
  }
  cout << '\n';
  return 0;
}

### Prompt

Please create a solution in CPP to the following problem:

Moamen was drawing a grid of n rows and 10^9 columns containing only digits 0 and 1. Ezzat noticed what Moamen was drawing and became interested in the minimum number of rows one needs to remove to make the grid beautiful.

A grid is beautiful if and only if for every two consecutive rows there is at least one column containing 1 in these two rows.

Ezzat will give you the number of rows n, and m segments of the grid that contain digits 1. Every segment is represented with three integers i, l, and r, where i represents the row number, and l and r represent the first and the last column of the segment in that row.

For example, if n = 3, m = 6, and the segments are (1,1,1), (1,7,8), (2,7,7), (2,15,15), (3,1,1), (3,15,15), then the grid is:

<image>

Your task is to tell Ezzat the minimum number of rows that should be removed to make the grid beautiful.

Input

The first line contains two integers n and m (1 ≤ n, m ≤ 3⋅10^5).

Each of the next m lines contains three integers i, l, and r (1 ≤ i ≤ n, 1 ≤ l ≤ r ≤ 10^9). Each of these m lines means that row number i contains digits 1 in columns from l to r, inclusive.

Note that the segments may overlap.

Output

In the first line, print a single integer k — the minimum number of rows that should be removed.

In the second line print k distinct integers r_1, r_2, …, r_k, representing the rows that should be removed (1 ≤ r_i ≤ n), in any order.

If there are multiple answers, print any.

Examples

Input


3 6
1 1 1
1 7 8
2 7 7
2 15 15
3 1 1
3 15 15


Output


0


Input


5 4
1 2 3
2 4 6
3 3 5
5 1 1


Output


3
2 4 5

Note

In the first test case, the grid is the one explained in the problem statement. The grid has the following properties: 

  1. The 1-st row and the 2-nd row have a common 1 in the column 7. 
  2. The 2-nd row and the 3-rd row have a common 1 in the column 15. 

As a result, this grid is beautiful and we do not need to remove any row.

In the second test case, the given grid is as follows: 

<image>

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
const long long INF = 0x3f3f3f3f;
const long long MOD = 998244353;
const long long N = 6e5 + 10;
struct SEG {
  struct Node {
    long long l, r, mx, idx, cg;
  } t[N << 2];
  void build(long long p, long long l, long long r) {
    t[p].l = l, t[p].r = r;
    t[p].mx = 0, t[p].cg = t[p].idx = -1;
    if (l == r) {
      return;
    }
    long long mid = (l + r) >> 1;
    build((p << 1), l, mid);
    build((p << 1 | 1), mid + 1, r);
  }
  void calc(long long p, long long x, long long id) {
    t[p].mx = t[p].cg = x;
    t[p].idx = id;
  }
  void pushdown(long long p) {
    if (t[p].cg != -1) {
      calc((p << 1), t[p].cg, t[p].idx);
      calc((p << 1 | 1), t[p].cg, t[p].idx);
      t[p].cg = -1;
    }
  }
  void pushup(long long p) {
    t[p].mx = max(t[(p << 1)].mx, t[(p << 1 | 1)].mx);
    t[p].idx = (t[(p << 1)].mx >= t[(p << 1 | 1)].mx) ? t[(p << 1)].idx
                                                      : t[(p << 1 | 1)].idx;
  }
  void update(long long p, long long l, long long r, long long x,
              long long id) {
    if (t[p].l > r || t[p].r < l) return;
    if (t[p].l >= l && t[p].r <= r) {
      calc(p, x, id);
      return;
    }
    pushdown(p);
    update((p << 1), l, r, x, id);
    update((p << 1 | 1), l, r, x, id);
    pushup(p);
  }
  pair<long long, long long> query(long long p, long long l, long long r) {
    if (t[p].l > r || t[p].r < l) return make_pair(0, -1);
    if (t[p].l >= l && t[p].r <= r) {
      return make_pair(t[p].mx, t[p].idx);
    }
    pushdown(p);
    pair<long long, long long> L = query((p << 1), l, r),
                               R = query((p << 1 | 1), l, r);
    return (L.first >= R.first) ? L : R;
  }
} seg;
signed main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  long long n, m;
  cin >> n >> m;
  vector<long long> hsh, pre(n, -1);
  vector<vector<pair<long long, long long> > > a(n);
  for (long long i = 0; i < m; i++) {
    long long id, l, r;
    cin >> id >> l >> r;
    a[id - 1].push_back({l, r});
    hsh.push_back(l);
    hsh.push_back(r);
  }
  sort(hsh.begin(), hsh.end());
  hsh.resize(unique(hsh.begin(), hsh.end()) - hsh.begin());
  seg.build(1, 0, hsh.size() - 1);
  for (long long i = 0; i < n; i++) {
    long long mx = 0, prt = -1;
    for (auto &j : a[i]) {
      j.first = lower_bound(hsh.begin(), hsh.end(), j.first) - hsh.begin();
      j.second = lower_bound(hsh.begin(), hsh.end(), j.second) - hsh.begin();
      pair<long long, long long> tmp = seg.query(1, j.first, j.second);
      if (tmp.first > mx) {
        mx = tmp.first;
        prt = tmp.second;
      }
    }
    pre[i] = prt;
    for (auto j : a[i]) {
      seg.update(1, j.first, j.second, mx + 1, i);
    }
  }
  cout << n - seg.t[1].mx << '\n';
  vector<long long> vis(n);
  for (long long i = seg.t[1].idx; i >= 0; i = pre[i]) {
    vis[i] = 1;
  }
  for (long long i = 0; i < n; i++) {
    if (!vis[i]) {
      cout << i + 1 << ' ';
    }
  }
  cout << '\n';
  return 0;
}

```