#include <bits/stdc++.h>
using namespace std;
const int MAXN = 3e5 + 7;
const int BASE = 1 << 30;
const int INF = 1e9 + 7;
struct segment_tree {
  vector<pair<int, int>> values;
  vector<pair<int, int>> nxt;
  vector<pair<int, int>> add;
  int size;
  segment_tree() {
    size = -1;
    newVertex();
  }
  void newVertex() {
    ++size;
    values.push_back({0, -1});
    nxt.push_back({-1, -1});
    add.push_back({0, -1});
  }
  pair<int, int> best(pair<int, int> lhs, pair<int, int> rhs) {
    if (lhs.first < rhs.first) return lhs;
    return rhs;
  }
  void push(int v) {
    int l = nxt[v].first;
    int r = nxt[v].second;
    if (l == -1) {
      newVertex();
      nxt[v].first = l = size;
    }
    if (r == -1) {
      newVertex();
      nxt[v].second = r = size;
    }
    values[l] = best(values[l], add[v]);
    values[r] = best(values[r], add[v]);
    add[l] = best(add[l], add[v]);
    add[r] = best(add[r], add[v]);
    add[v] = {INF, -1};
  }
  pair<int, int> minn(int l, int r, int v = 0, int b = 0, int e = BASE - 1) {
    if (r < b || e < l) return {INF, -1};
    if (l <= b && e <= r) return values[v];
    push(v);
    int mid = (b + e) / 2;
    pair<int, int> lVal = minn(l, r, nxt[v].first, b, mid);
    pair<int, int> rVal = minn(l, r, nxt[v].second, mid + 1, e);
    values[v] = best(values[nxt[v].first], values[nxt[v].second]);
    return best(lVal, rVal);
  }
  void change(int l, int r, pair<int, int> val, int v = 0, int b = 0,
              int e = BASE - 1) {
    if (r < b || e < l) return;
    if (l <= b && e <= r) {
      add[v] = val;
      values[v] = val;
      return;
    }
    push(v);
    int mid = (b + e) / 2;
    change(l, r, val, nxt[v].first, b, mid);
    change(l, r, val, nxt[v].second, mid + 1, e);
    values[v] = best(values[nxt[v].first], values[nxt[v].second]);
  }
};
vector<pair<int, int>> segments[MAXN];
int dp[MAXN];
int prv[MAXN];
bool ok[MAXN];
void solve() {
  segment_tree tree;
  int n, m;
  cin >> n >> m;
  map<int, int> scaled;
  vector<int> sorted;
  for (int i = 1; i <= m; ++i) {
    int h, l, r;
    cin >> h >> l >> r;
    segments[h].push_back({l, r});
    sorted.push_back(l);
    sorted.push_back(r);
  }
  sort(sorted.begin(), sorted.end());
  int last = -1;
  int cnt = 0;
  for (int i = 0; i < sorted.size(); ++i) {
    if (sorted[i] != last) {
      scaled[sorted[i]] = ++cnt;
      last = sorted[i];
    }
  }
  for (int h = 1; h <= n; ++h) {
    for (auto& [l, r] : segments[h]) {
      l = scaled[l];
      r = scaled[r];
    }
  }
  for (int h = 1; h <= n; ++h) {
    dp[h] = INF;
    for (auto [l, r] : segments[h]) {
      auto [val, ind] = tree.minn(l, r);
      if (val + h - 1 < dp[h]) {
        dp[h] = val + h - 1;
        prv[h] = ind;
      }
    }
    for (auto [l, r] : segments[h]) {
      tree.change(l, r, {dp[h] - h, h});
    }
  }
  auto [ans, ind] = tree.minn(0, BASE - 1);
  cout << ans + n << '\n';
  while (ind != 0) {
    ok[ind] = true;
    ind = prv[ind];
  }
  for (int i = 1; i <= n; ++i) {
    if (!ok[i]) cout << i << ' ';
  }
  cout << '\n';
}
int main() {
  ios_base::sync_with_stdio(0), cin.tie(0);
  int T;
  T = 1;
  while (T--) solve();
  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;
const int MAXN = 3e5 + 7;
const int BASE = 1 << 30;
const int INF = 1e9 + 7;
struct segment_tree {
  vector<pair<int, int>> values;
  vector<pair<int, int>> nxt;
  vector<pair<int, int>> add;
  int size;
  segment_tree() {
    size = -1;
    newVertex();
  }
  void newVertex() {
    ++size;
    values.push_back({0, -1});
    nxt.push_back({-1, -1});
    add.push_back({0, -1});
  }
  pair<int, int> best(pair<int, int> lhs, pair<int, int> rhs) {
    if (lhs.first < rhs.first) return lhs;
    return rhs;
  }
  void push(int v) {
    int l = nxt[v].first;
    int r = nxt[v].second;
    if (l == -1) {
      newVertex();
      nxt[v].first = l = size;
    }
    if (r == -1) {
      newVertex();
      nxt[v].second = r = size;
    }
    values[l] = best(values[l], add[v]);
    values[r] = best(values[r], add[v]);
    add[l] = best(add[l], add[v]);
    add[r] = best(add[r], add[v]);
    add[v] = {INF, -1};
  }
  pair<int, int> minn(int l, int r, int v = 0, int b = 0, int e = BASE - 1) {
    if (r < b || e < l) return {INF, -1};
    if (l <= b && e <= r) return values[v];
    push(v);
    int mid = (b + e) / 2;
    pair<int, int> lVal = minn(l, r, nxt[v].first, b, mid);
    pair<int, int> rVal = minn(l, r, nxt[v].second, mid + 1, e);
    values[v] = best(values[nxt[v].first], values[nxt[v].second]);
    return best(lVal, rVal);
  }
  void change(int l, int r, pair<int, int> val, int v = 0, int b = 0,
              int e = BASE - 1) {
    if (r < b || e < l) return;
    if (l <= b && e <= r) {
      add[v] = val;
      values[v] = val;
      return;
    }
    push(v);
    int mid = (b + e) / 2;
    change(l, r, val, nxt[v].first, b, mid);
    change(l, r, val, nxt[v].second, mid + 1, e);
    values[v] = best(values[nxt[v].first], values[nxt[v].second]);
  }
};
vector<pair<int, int>> segments[MAXN];
int dp[MAXN];
int prv[MAXN];
bool ok[MAXN];
void solve() {
  segment_tree tree;
  int n, m;
  cin >> n >> m;
  map<int, int> scaled;
  vector<int> sorted;
  for (int i = 1; i <= m; ++i) {
    int h, l, r;
    cin >> h >> l >> r;
    segments[h].push_back({l, r});
    sorted.push_back(l);
    sorted.push_back(r);
  }
  sort(sorted.begin(), sorted.end());
  int last = -1;
  int cnt = 0;
  for (int i = 0; i < sorted.size(); ++i) {
    if (sorted[i] != last) {
      scaled[sorted[i]] = ++cnt;
      last = sorted[i];
    }
  }
  for (int h = 1; h <= n; ++h) {
    for (auto& [l, r] : segments[h]) {
      l = scaled[l];
      r = scaled[r];
    }
  }
  for (int h = 1; h <= n; ++h) {
    dp[h] = INF;
    for (auto [l, r] : segments[h]) {
      auto [val, ind] = tree.minn(l, r);
      if (val + h - 1 < dp[h]) {
        dp[h] = val + h - 1;
        prv[h] = ind;
      }
    }
    for (auto [l, r] : segments[h]) {
      tree.change(l, r, {dp[h] - h, h});
    }
  }
  auto [ans, ind] = tree.minn(0, BASE - 1);
  cout << ans + n << '\n';
  while (ind != 0) {
    ok[ind] = true;
    ind = prv[ind];
  }
  for (int i = 1; i <= n; ++i) {
    if (!ok[i]) cout << i << ' ';
  }
  cout << '\n';
}
int main() {
  ios_base::sync_with_stdio(0), cin.tie(0);
  int T;
  T = 1;
  while (T--) solve();
  return 0;
}

```