#include <bits/stdc++.h>
using namespace std;
const int N = 3e5 + 5;
pair<int, int> seg[8 * N], lazy[8 * N];
void build(int l, int u, int i) {
  lazy[i] = {3 * N, -1};
  seg[i] = {0, -1};
  if (l == u) return;
  build(l, ((l + u) / 2), (i * 2 + 1));
  build(((l + u) / 2) + 1, u, (i * 2 + 2));
}
void lazup(int l, int u, int i) {
  if (lazy[i].first == 3 * N) return;
  seg[i] = min(seg[i], lazy[i]);
  if (l != u) {
    lazy[(i * 2 + 1)] = min(lazy[(i * 2 + 1)], lazy[i]);
    lazy[(i * 2 + 2)] = min(lazy[(i * 2 + 2)], lazy[i]);
  }
  lazy[i] = {3 * N, -1};
}
pair<int, int> query(int l, int u, int i, int ll, int uu) {
  lazup(l, u, i);
  if (l >= ll && u <= uu) {
    return seg[i];
  }
  if (l > uu || u < ll) return {3 * N, -1};
  return min(query(l, ((l + u) / 2), (i * 2 + 1), ll, uu),
             query(((l + u) / 2) + 1, u, (i * 2 + 2), ll, uu));
}
pair<int, int> update(int l, int u, int i, int ll, int uu, pair<int, int> &x) {
  lazup(l, u, i);
  if (l >= ll && u <= uu) {
    lazy[i] = x;
    lazup(l, u, i);
    return seg[i];
  }
  if (l > uu || u < ll) return seg[i];
  return seg[i] = min(update(l, ((l + u) / 2), (i * 2 + 1), ll, uu, x),
                      update(((l + u) / 2) + 1, u, (i * 2 + 2), ll, uu, x));
}
signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  int n, m;
  cin >> n >> m;
  vector<pair<int, int>> r[n];
  map<int, int> mp;
  set<int> s;
  for (int i = 0; i < m; i++) {
    int x, ll, rr;
    cin >> x >> ll >> rr;
    r[x - 1].push_back({ll, rr});
    s.insert(ll);
    s.insert(rr);
  }
  int c = 0;
  for (int x : s) {
    mp[x] = c++;
  }
  int oset = 0;
  int dp[n], prev[n];
  build(0, c - 1, 0);
  int ans = n, curr = -1;
  for (int i = 0; i < n; i++) {
    dp[i] = i;
    prev[i] = -1;
    for (pair<int, int> k : r[i]) {
      pair<int, int> lol = query(0, c - 1, 0, mp[k.first], mp[k.second]);
      if ((lol.first + oset) < dp[i]) {
        dp[i] = lol.first + oset;
        prev[i] = lol.second;
      }
    }
    pair<int, int> x = {dp[i] - (oset + 1), i};
    for (pair<int, int> k : r[i]) {
      update(0, c - 1, 0, mp[k.first], mp[k.second], x);
    }
    ans = min(ans, dp[i] + (n - i - 1));
    if (ans == (dp[i] + n - i - 1)) curr = i;
    oset++;
  }
  cout << ans << endl;
  int currind = n - 1;
  while (currind >= 0) {
    while (currind > curr) {
      cout << (currind + 1) << " ";
      currind--;
    }
    if (curr == -1)
      currind = -1;
    else {
      curr = prev[curr];
      currind--;
    }
  }
}

### Prompt

In CPP, your task is to solve 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 N = 3e5 + 5;
pair<int, int> seg[8 * N], lazy[8 * N];
void build(int l, int u, int i) {
  lazy[i] = {3 * N, -1};
  seg[i] = {0, -1};
  if (l == u) return;
  build(l, ((l + u) / 2), (i * 2 + 1));
  build(((l + u) / 2) + 1, u, (i * 2 + 2));
}
void lazup(int l, int u, int i) {
  if (lazy[i].first == 3 * N) return;
  seg[i] = min(seg[i], lazy[i]);
  if (l != u) {
    lazy[(i * 2 + 1)] = min(lazy[(i * 2 + 1)], lazy[i]);
    lazy[(i * 2 + 2)] = min(lazy[(i * 2 + 2)], lazy[i]);
  }
  lazy[i] = {3 * N, -1};
}
pair<int, int> query(int l, int u, int i, int ll, int uu) {
  lazup(l, u, i);
  if (l >= ll && u <= uu) {
    return seg[i];
  }
  if (l > uu || u < ll) return {3 * N, -1};
  return min(query(l, ((l + u) / 2), (i * 2 + 1), ll, uu),
             query(((l + u) / 2) + 1, u, (i * 2 + 2), ll, uu));
}
pair<int, int> update(int l, int u, int i, int ll, int uu, pair<int, int> &x) {
  lazup(l, u, i);
  if (l >= ll && u <= uu) {
    lazy[i] = x;
    lazup(l, u, i);
    return seg[i];
  }
  if (l > uu || u < ll) return seg[i];
  return seg[i] = min(update(l, ((l + u) / 2), (i * 2 + 1), ll, uu, x),
                      update(((l + u) / 2) + 1, u, (i * 2 + 2), ll, uu, x));
}
signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  int n, m;
  cin >> n >> m;
  vector<pair<int, int>> r[n];
  map<int, int> mp;
  set<int> s;
  for (int i = 0; i < m; i++) {
    int x, ll, rr;
    cin >> x >> ll >> rr;
    r[x - 1].push_back({ll, rr});
    s.insert(ll);
    s.insert(rr);
  }
  int c = 0;
  for (int x : s) {
    mp[x] = c++;
  }
  int oset = 0;
  int dp[n], prev[n];
  build(0, c - 1, 0);
  int ans = n, curr = -1;
  for (int i = 0; i < n; i++) {
    dp[i] = i;
    prev[i] = -1;
    for (pair<int, int> k : r[i]) {
      pair<int, int> lol = query(0, c - 1, 0, mp[k.first], mp[k.second]);
      if ((lol.first + oset) < dp[i]) {
        dp[i] = lol.first + oset;
        prev[i] = lol.second;
      }
    }
    pair<int, int> x = {dp[i] - (oset + 1), i};
    for (pair<int, int> k : r[i]) {
      update(0, c - 1, 0, mp[k.first], mp[k.second], x);
    }
    ans = min(ans, dp[i] + (n - i - 1));
    if (ans == (dp[i] + n - i - 1)) curr = i;
    oset++;
  }
  cout << ans << endl;
  int currind = n - 1;
  while (currind >= 0) {
    while (currind > curr) {
      cout << (currind + 1) << " ";
      currind--;
    }
    if (curr == -1)
      currind = -1;
    else {
      curr = prev[curr];
      currind--;
    }
  }
}

```