Problem: This year Alex has finished school, and now he is a first-year student of Berland State University. For him it was a total surprise that even though he studies programming, he still has to attend physical education lessons. The end of the term is very soon, but, unfortunately, Alex still hasn't attended a single lesson!

Since Alex doesn't want to get expelled, he wants to know the number of working days left until the end of the term, so he can attend physical education lessons during these days. But in BSU calculating the number of working days is a complicated matter:

There are n days left before the end of the term (numbered from 1 to n), and initially all of them are working days. Then the university staff sequentially publishes q orders, one after another. Each order is characterised by three numbers l, r and k:

  * If k = 1, then all days from l to r (inclusive) become non-working days. If some of these days are made working days by some previous order, then these days still become non-working days; 
  * If k = 2, then all days from l to r (inclusive) become working days. If some of these days are made non-working days by some previous order, then these days still become working days. 



Help Alex to determine the number of working days left after each order!

Input

The first line contains one integer n, and the second line — one integer q (1 ≤ n ≤ 109, 1 ≤ q ≤ 3·105) — the number of days left before the end of the term, and the number of orders, respectively.

Then q lines follow, i-th line containing three integers li, ri and ki representing i-th order (1 ≤ li ≤ ri ≤ n, 1 ≤ ki ≤ 2).

Output

Print q integers. i-th of them must be equal to the number of working days left until the end of the term after the first i orders are published.

Example

Input

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


Output

2
0
2
3
1
4

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
const int mod = 1e9 + 7, inf = 1e9, N = 500 + 2;
const ll MOD = 1e9 + 7, INF = 1e19;
ld tic, tac;
int tc = 1;
using Data = int;
using Lazy = int;
const Data vid = 0, qid = 0;
const Lazy lid = -1;
template <const int MXSZ, const int MAXROOTS, const bool INDEXING>
struct AdvanceSegTree {
  Data merge(const Data &l, const Data &r) { return l + r; }
  Data apply(const Data &x, const Lazy &v) { return v; }
  Lazy getSegmentVal(const Lazy &v, int len) { return v * len; }
  Lazy mergeLazy(const Lazy &l, const Lazy &r) { return r; }
  int N, roots[MAXROOTS], L[MXSZ], R[MXSZ];
  Data VAL[MXSZ], LZ[MXSZ], curNode = 0, curRoot = 0;
  int newNode(int cp = 0) {
    assert(curNode < MXSZ);
    L[curNode] = curNode ? L[cp] : 0;
    R[curNode] = curNode ? R[cp] : 0;
    VAL[curNode] = curNode ? VAL[cp] : vid;
    LZ[curNode] = curNode ? LZ[cp] : lid;
    return curNode++;
  }
  void propagate(int cur, int cL, int cR) {
    if (LZ[cur] != lid) {
      int m = cL + (cR - cL) / 2;
      if (!L[cur]) L[cur] = newNode();
      VAL[L[cur]] = apply(VAL[L[cur]], getSegmentVal(LZ[cur], m - cL + 1));
      LZ[L[cur]] = mergeLazy(LZ[L[cur]], LZ[cur]);
      if (!R[cur]) R[cur] = newNode();
      VAL[R[cur]] = apply(VAL[R[cur]], getSegmentVal(LZ[cur], cR - m));
      LZ[R[cur]] = mergeLazy(LZ[R[cur]], LZ[cur]);
      LZ[cur] = lid;
    }
  }
  template <class It>
  int build(int cL, int cR, It st) {
    int ret = newNode();
    if (cL == cR) {
      VAL[ret] = *(st + cL - INDEXING);
      return ret;
    }
    int m = cL + (cR - cL) / 2;
    L[ret] = build(cL, m, st);
    R[ret] = build(m + 1, cR, st);
    VAL[ret] = merge(VAL[L[ret]], VAL[R[ret]]);
    return ret;
  }
  int update(int cur, int cL, int cR, int l, int r, const Lazy &val,
             bool persistent) {
    if (cL > r || cR < l) return cur;
    int ret = persistent ? newNode(cur) : cur;
    if (cL >= l && cR <= r) {
      VAL[ret] = apply(VAL[ret], getSegmentVal(val, cR - cL + 1));
      LZ[ret] = mergeLazy(LZ[ret], val);
      return ret;
    }
    if (!L[ret]) L[ret] = newNode();
    if (!R[ret]) R[ret] = newNode();
    int m = cL + (cR - cL) / 2;
    propagate(ret, cL, cR);
    L[ret] = update(L[ret], cL, m, l, r, val, persistent);
    R[ret] = update(R[ret], m + 1, cR, l, r, val, persistent);
    if (L[ret] && R[ret])
      VAL[ret] = merge(VAL[L[ret]], VAL[R[ret]]);
    else if (L[ret])
      VAL[ret] = merge(VAL[L[ret]], Data(vid));
    else if (R[ret])
      VAL[ret] = merge(VAL[R[ret]], Data(vid));
    return ret;
  }
  Data query(int cur, int cL, int cR, int l, int r) {
    if (cL > r || cR < l) return qid;
    if (!cur) return vid;
    if (cL >= l && cR <= r) return VAL[cur];
    int m = cL + (cR - cL) / 2;
    propagate(cur, cL, cR);
    return merge(query(L[cur], cL, m, l, r), query(R[cur], m + 1, cR, l, r));
  }
  template <class It>
  void init(It st, It en) {
    N = en - st;
    newNode();
    roots[curRoot++] = build(INDEXING, N - !INDEXING, st);
  }
  void init(int size) {
    N = size;
    newNode();
    roots[curRoot++] = newNode();
  }
  void update(int l, int r, Lazy val, bool persistent = false) {
    int nr = update(roots[curRoot - 1], INDEXING, N - !INDEXING, l, r, val,
                    persistent);
    if (persistent)
      roots[curRoot++] = nr;
    else
      roots[curRoot - 1] = nr;
  }
  Data query(int l, int r, int rootInd = -1) {
    return query((rootInd == -1 ? roots[curRoot - 1] : roots[rootInd]),
                 INDEXING, N - !INDEXING, l, r);
  }
  void revert(int x) { roots[curRoot++] = roots[x]; }
  void clear() { curNode = curRoot = 0; }
};
int n, q, l, r, k;
AdvanceSegTree<15000005, 1, 1> tree;
void solve() {
  cin >> n >> q;
  tree.init(n);
  for (ll i = (0) - (1 - 2 * (0 > q) < 0);
       (1 - 2 * (0 > q)) > 0 ? i < (q) : i >= (q); i += (1 - 2 * (0 > q))) {
    cin >> l >> r >> k;
    tree.update(l, r, k % 2);
    cout << n - tree.query(1, n) << '\n';
  }
}
int main() {
  ios::sync_with_stdio(0);
  cout.tie(0);
  cin.tie(0);
  cout << fixed << setprecision(10);
  if (tc != 1) cin >> tc;
  for (int i = 1; i <= tc; ++i) {
    if (!1) cerr << "\nWhile solving TC " << i << ":\n", tic = clock();
    solve();
    if (!1)
      tac = clock(), cerr << "\nTC " << i << " done in:: "
                          << 1000 * (tac - tic) / CLOCKS_PER_SEC << " ms\n";
  }
  if (!1)
    cerr << "\nGG in: " << 1000 * ((ld)clock()) / CLOCKS_PER_SEC << " ms\n";
  return 0;
}