#include <bits/stdc++.h>
using namespace std;
mt19937 rnd(time(0));
struct Node {
  int val, pos;
  bool operator<(const Node& ot) const { return val < ot.val; }
};
struct lazy_segment_tree {
  static const int N = 1e6 + 10;
  const Node good_value = {0, 0};
  Node t[4 * N], ch[4 * N];
  Node merge(Node a, Node b) { return max(a, b); }
  void build(int v = 1, int tl = 1, int tr = N - 1) {
    if (tl == tr) {
      t[v] = {0, 0};
      return;
    }
    int tm = (tl + tr) / 2;
    build(v + v, tl, tm);
    build(v + v + 1, tm + 1, tr);
    t[v] = merge(t[v + v], t[v + v + 1]);
  }
  void push(int v, int tl, int tr) {
    if (!ch[v].val) return;
    t[v] = ch[v];
    if (tl < tr) {
      ch[v + v] = ch[v];
      ch[v + v + 1] = ch[v];
    }
    ch[v] = {0, 0};
  }
  void update(int l, int r, Node x, int v = 1, int tl = 1, int tr = N - 1) {
    push(v, tl, tr);
    if (r < tl || tr < l) return;
    if (l <= tl && tr <= r) {
      ch[v] = x;
      push(v, tl, tr);
      return;
    }
    int tm = (tl + tr) / 2;
    update(l, r, x, v + v, tl, tm);
    update(l, r, x, v + v + 1, tm + 1, tr);
    t[v] = merge(t[v + v], t[v + v + 1]);
  }
  Node get(int l, int r, int v = 1, int tl = 1, int tr = N - 1) {
    push(v, tl, tr);
    if (r < tl || tr < l) return good_value;
    if (l <= tl && tr <= r) return t[v];
    int tm = (tl + tr) / 2;
    Node res =
        merge(get(l, r, v + v, tl, tm), get(l, r, v + v + 1, tm + 1, tr));
    t[v] = merge(t[v + v], t[v + v + 1]);
    return res;
  }
} tree;
const int N = 3e5 + 10;
vector<pair<int, int> > a[N];
vector<int> all;
map<int, int> mp;
int mem[N];
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int n, m;
  cin >> n >> m;
  for (int i = 1; i <= m; i++) {
    int id, l, r;
    cin >> id >> l >> r;
    a[id].push_back({l, r});
    all.push_back(l);
    all.push_back(r);
  }
  sort(all.begin(), all.end());
  all.erase(unique(all.begin(), all.end()), all.end());
  for (int i = 0; i < all.size(); i++) {
    mp[all[i]] = i + 1;
  }
  tree.build();
  for (int i = 1; i <= n; i++) {
    int cur = 0;
    for (auto& [l, r] : a[i]) {
      l = mp[l];
      r = mp[r];
      Node tmp = tree.get(l, r);
      tmp.val++;
      if (cur < tmp.val) {
        cur = tmp.val;
        mem[i] = tmp.pos;
      }
    }
    for (int j = 0; j < a[i].size(); j++) {
      tree.update(a[i][j].first, a[i][j].second, {cur, i});
    }
  }
  Node res = tree.get(1, tree.N - 1);
  cout << n - res.val << "\n";
  vector<int> ans;
  int ptr = res.pos;
  for (int i = n; i >= ptr + 1; i--) {
    ans.push_back(i);
  }
  while (ptr != mem[ptr]) {
    for (int i = ptr - 1; i >= mem[ptr] + 1; i--) {
      ans.push_back(i);
    }
    ptr = mem[ptr];
  }
  reverse(ans.begin(), ans.end());
  for (int i : ans) {
    cout << i << " ";
  }
  cout << "\n";
  return 0;
}

### Prompt

Create a solution in cpp for 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;
mt19937 rnd(time(0));
struct Node {
  int val, pos;
  bool operator<(const Node& ot) const { return val < ot.val; }
};
struct lazy_segment_tree {
  static const int N = 1e6 + 10;
  const Node good_value = {0, 0};
  Node t[4 * N], ch[4 * N];
  Node merge(Node a, Node b) { return max(a, b); }
  void build(int v = 1, int tl = 1, int tr = N - 1) {
    if (tl == tr) {
      t[v] = {0, 0};
      return;
    }
    int tm = (tl + tr) / 2;
    build(v + v, tl, tm);
    build(v + v + 1, tm + 1, tr);
    t[v] = merge(t[v + v], t[v + v + 1]);
  }
  void push(int v, int tl, int tr) {
    if (!ch[v].val) return;
    t[v] = ch[v];
    if (tl < tr) {
      ch[v + v] = ch[v];
      ch[v + v + 1] = ch[v];
    }
    ch[v] = {0, 0};
  }
  void update(int l, int r, Node x, int v = 1, int tl = 1, int tr = N - 1) {
    push(v, tl, tr);
    if (r < tl || tr < l) return;
    if (l <= tl && tr <= r) {
      ch[v] = x;
      push(v, tl, tr);
      return;
    }
    int tm = (tl + tr) / 2;
    update(l, r, x, v + v, tl, tm);
    update(l, r, x, v + v + 1, tm + 1, tr);
    t[v] = merge(t[v + v], t[v + v + 1]);
  }
  Node get(int l, int r, int v = 1, int tl = 1, int tr = N - 1) {
    push(v, tl, tr);
    if (r < tl || tr < l) return good_value;
    if (l <= tl && tr <= r) return t[v];
    int tm = (tl + tr) / 2;
    Node res =
        merge(get(l, r, v + v, tl, tm), get(l, r, v + v + 1, tm + 1, tr));
    t[v] = merge(t[v + v], t[v + v + 1]);
    return res;
  }
} tree;
const int N = 3e5 + 10;
vector<pair<int, int> > a[N];
vector<int> all;
map<int, int> mp;
int mem[N];
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int n, m;
  cin >> n >> m;
  for (int i = 1; i <= m; i++) {
    int id, l, r;
    cin >> id >> l >> r;
    a[id].push_back({l, r});
    all.push_back(l);
    all.push_back(r);
  }
  sort(all.begin(), all.end());
  all.erase(unique(all.begin(), all.end()), all.end());
  for (int i = 0; i < all.size(); i++) {
    mp[all[i]] = i + 1;
  }
  tree.build();
  for (int i = 1; i <= n; i++) {
    int cur = 0;
    for (auto& [l, r] : a[i]) {
      l = mp[l];
      r = mp[r];
      Node tmp = tree.get(l, r);
      tmp.val++;
      if (cur < tmp.val) {
        cur = tmp.val;
        mem[i] = tmp.pos;
      }
    }
    for (int j = 0; j < a[i].size(); j++) {
      tree.update(a[i][j].first, a[i][j].second, {cur, i});
    }
  }
  Node res = tree.get(1, tree.N - 1);
  cout << n - res.val << "\n";
  vector<int> ans;
  int ptr = res.pos;
  for (int i = n; i >= ptr + 1; i--) {
    ans.push_back(i);
  }
  while (ptr != mem[ptr]) {
    for (int i = ptr - 1; i >= mem[ptr] + 1; i--) {
      ans.push_back(i);
    }
    ptr = mem[ptr];
  }
  reverse(ans.begin(), ans.end());
  for (int i : ans) {
    cout << i << " ";
  }
  cout << "\n";
  return 0;
}

```