#include <bits/stdc++.h>
using namespace std;
struct data {
  long long id, l, r;
  bool operator<(const data &a) const { return id < a.id; }
};
const long long N = 6e5 + 10;
long long n;
long long m;
data a[N];
struct Interval_Tree {
  pair<long long, long long> node[4 * N];
  pair<long long, long long> lazy[4 * N];
  Interval_Tree() {}
  void Down(long long i) {
    if (node[2 * i].first < lazy[i].first) {
      node[2 * i] = lazy[i];
    }
    if (node[2 * i + 1].first < lazy[i].first) {
      node[2 * i + 1] = lazy[i];
    }
    if (lazy[2 * i].first < lazy[i].first) {
      lazy[2 * i] = lazy[i];
    }
    if (lazy[2 * i + 1].first < lazy[i].first) {
      lazy[2 * i + 1] = lazy[i];
    }
    lazy[i] = {0, 0};
  }
  void update(long long i, long long l, long long r, long long x, long long y,
              long long val, long long id) {
    if (l > y || x > r) {
      return;
    }
    if (x <= l && r <= y) {
      if (node[i].first < val) {
        node[i] = {val, id};
      }
      if (lazy[i].first < val) {
        lazy[i] = {val, id};
      }
      return;
    }
    Down(i);
    long long mid = (l + r) / 2;
    update(2 * i, l, mid, x, y, val, id);
    update(2 * i + 1, mid + 1, r, x, y, val, id);
    if (node[2 * i].first < node[2 * i + 1].first) {
      node[i] = node[2 * i + 1];
    } else {
      node[i] = node[2 * i];
    }
  }
  pair<long long, long long> get(long long i, long long l, long long r,
                                 long long x, long long y) {
    if (l > y || x > r) {
      return {0, 0};
    }
    if (x <= l && r <= y) {
      return node[i];
    }
    Down(i);
    long long mid = (l + r) / 2;
    pair<long long, long long> tmp1 = get(2 * i, l, mid, x, y);
    pair<long long, long long> tmp2 = get(2 * i + 1, mid + 1, r, x, y);
    if (tmp1.first < tmp2.first) {
      return tmp2;
    } else {
      return tmp1;
    }
  }
} IT;
long long maxVal;
void compress() {
  vector<long long> rar;
  for (long long i = 1; i <= m; ++i) {
    rar.push_back(a[i].l);
    rar.push_back(a[i].r);
  }
  sort(rar.begin(), rar.end());
  rar.resize(unique(rar.begin(), rar.end()) - rar.begin());
  for (long long i = 1; i <= m; ++i) {
    a[i].l = lower_bound(rar.begin(), rar.end(), a[i].l) - rar.begin() + 1;
    a[i].r = lower_bound(rar.begin(), rar.end(), a[i].r) - rar.begin() + 1;
  }
  maxVal = (long long)rar.size() + 1;
}
vector<long long> V;
bool mark[N];
pair<long long, long long> dp[N];
void sol() {
  compress();
  sort(a + 1, a + m + 1);
  IT.update(1, 1, maxVal, 1, maxVal, 0, 0);
  for (long long l = 1; l <= m; ++l) {
    long long r = l;
    while (r <= m && a[r].id == a[l].id) {
      ++r;
    }
    --r;
    for (long long i = l; i <= r; ++i) {
      long long id = a[i].id;
      pair<long long, long long> tmp = IT.get(1, 1, maxVal, a[i].l, a[i].r);
      if (dp[id].first < tmp.first + 1) {
        dp[id] = {tmp.first + 1, tmp.second};
      }
    }
    for (long long i = l; i <= r; ++i) {
      long long id = a[i].id;
      IT.update(1, 1, maxVal, a[i].l, a[i].r, dp[id].first, id);
    }
    l = r;
  }
  long long res = 0;
  long long save = -1;
  for (long long i = 1; i <= n; ++i) {
    if (res < dp[i].first) {
      res = dp[i].first;
      save = i;
    }
  }
  while (save > 0) {
    mark[save] = true;
    save = dp[save].second;
  }
  for (long long i = 1; i <= n; ++i) {
    if (!mark[i]) {
      V.push_back(i);
    }
  }
  cout << V.size() << '\n';
  for (long long r : V) {
    cout << r << " ";
  }
  cout << '\n';
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  if (fopen("input.txt", "r")) {
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
  }
  cin >> n >> m;
  for (long long i = 1; i <= m; ++i) {
    long long id, l, r;
    cin >> id >> l >> r;
    a[i] = {id, l, r};
  }
  sol();
  return 0;
}

### Prompt

Your task is to create a Cpp solution 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;
struct data {
  long long id, l, r;
  bool operator<(const data &a) const { return id < a.id; }
};
const long long N = 6e5 + 10;
long long n;
long long m;
data a[N];
struct Interval_Tree {
  pair<long long, long long> node[4 * N];
  pair<long long, long long> lazy[4 * N];
  Interval_Tree() {}
  void Down(long long i) {
    if (node[2 * i].first < lazy[i].first) {
      node[2 * i] = lazy[i];
    }
    if (node[2 * i + 1].first < lazy[i].first) {
      node[2 * i + 1] = lazy[i];
    }
    if (lazy[2 * i].first < lazy[i].first) {
      lazy[2 * i] = lazy[i];
    }
    if (lazy[2 * i + 1].first < lazy[i].first) {
      lazy[2 * i + 1] = lazy[i];
    }
    lazy[i] = {0, 0};
  }
  void update(long long i, long long l, long long r, long long x, long long y,
              long long val, long long id) {
    if (l > y || x > r) {
      return;
    }
    if (x <= l && r <= y) {
      if (node[i].first < val) {
        node[i] = {val, id};
      }
      if (lazy[i].first < val) {
        lazy[i] = {val, id};
      }
      return;
    }
    Down(i);
    long long mid = (l + r) / 2;
    update(2 * i, l, mid, x, y, val, id);
    update(2 * i + 1, mid + 1, r, x, y, val, id);
    if (node[2 * i].first < node[2 * i + 1].first) {
      node[i] = node[2 * i + 1];
    } else {
      node[i] = node[2 * i];
    }
  }
  pair<long long, long long> get(long long i, long long l, long long r,
                                 long long x, long long y) {
    if (l > y || x > r) {
      return {0, 0};
    }
    if (x <= l && r <= y) {
      return node[i];
    }
    Down(i);
    long long mid = (l + r) / 2;
    pair<long long, long long> tmp1 = get(2 * i, l, mid, x, y);
    pair<long long, long long> tmp2 = get(2 * i + 1, mid + 1, r, x, y);
    if (tmp1.first < tmp2.first) {
      return tmp2;
    } else {
      return tmp1;
    }
  }
} IT;
long long maxVal;
void compress() {
  vector<long long> rar;
  for (long long i = 1; i <= m; ++i) {
    rar.push_back(a[i].l);
    rar.push_back(a[i].r);
  }
  sort(rar.begin(), rar.end());
  rar.resize(unique(rar.begin(), rar.end()) - rar.begin());
  for (long long i = 1; i <= m; ++i) {
    a[i].l = lower_bound(rar.begin(), rar.end(), a[i].l) - rar.begin() + 1;
    a[i].r = lower_bound(rar.begin(), rar.end(), a[i].r) - rar.begin() + 1;
  }
  maxVal = (long long)rar.size() + 1;
}
vector<long long> V;
bool mark[N];
pair<long long, long long> dp[N];
void sol() {
  compress();
  sort(a + 1, a + m + 1);
  IT.update(1, 1, maxVal, 1, maxVal, 0, 0);
  for (long long l = 1; l <= m; ++l) {
    long long r = l;
    while (r <= m && a[r].id == a[l].id) {
      ++r;
    }
    --r;
    for (long long i = l; i <= r; ++i) {
      long long id = a[i].id;
      pair<long long, long long> tmp = IT.get(1, 1, maxVal, a[i].l, a[i].r);
      if (dp[id].first < tmp.first + 1) {
        dp[id] = {tmp.first + 1, tmp.second};
      }
    }
    for (long long i = l; i <= r; ++i) {
      long long id = a[i].id;
      IT.update(1, 1, maxVal, a[i].l, a[i].r, dp[id].first, id);
    }
    l = r;
  }
  long long res = 0;
  long long save = -1;
  for (long long i = 1; i <= n; ++i) {
    if (res < dp[i].first) {
      res = dp[i].first;
      save = i;
    }
  }
  while (save > 0) {
    mark[save] = true;
    save = dp[save].second;
  }
  for (long long i = 1; i <= n; ++i) {
    if (!mark[i]) {
      V.push_back(i);
    }
  }
  cout << V.size() << '\n';
  for (long long r : V) {
    cout << r << " ";
  }
  cout << '\n';
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  if (fopen("input.txt", "r")) {
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
  }
  cin >> n >> m;
  for (long long i = 1; i <= m; ++i) {
    long long id, l, r;
    cin >> id >> l >> r;
    a[i] = {id, l, r};
  }
  sol();
  return 0;
}

```