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 JAVA):

Solution:
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.StringTokenizer;
import java.util.Random;
import java.io.IOException;
import java.util.InputMismatchException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author Darkhan Imangaliyev
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        QuickScanner in = new QuickScanner(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        TaskE solver = new TaskE();
        solver.solve(1, in, out);
        out.close();
    }

    static class TaskE {
        int n;
        final static Random rnd = new Random();

        public void solve(int testNumber, QuickScanner in, PrintWriter out) {
            n = in.nextInt();
            int m = in.nextInt();
            int[] l = new int[m];
            int[] r = new int[m];
            int[] op = new int[m];
            for (int i = 0; i < m; ++i) {
                l[i] = in.nextInt();
                r[i] = in.nextInt();
                op[i] = in.nextInt() - 1;
            }

            int[] arr = new int[2 * m + 2];
            int at = 0;
            arr[at++] = 1;
            arr[at++] = n + 1;
            for (int i = 0; i < m; ++i) {
                arr[at++] = l[i];
                arr[at++] = r[i] + 1;
            }
            shuffle(arr);
            Arrays.sort(arr);
            int size = 0;
            for (int i = 1; i < arr.length; ++i) {
                if (arr[size] != arr[i]) {
                    arr[++size] = arr[i];
                }
            }

            int[] b = new int[size + 1];
            for (int i = 0; i < size; ++i) {
                b[i] = arr[i + 1] - arr[i];
            }
//        System.out.println("Segments = " + Arrays.toString(b));

            final TaskE.LazySegmentTree tree = new TaskE.LazySegmentTree(b);

            for (int q = 0; q < m; ++q) {
                int lo = binarySearch(arr, l[q], size + 1);
                int hi = binarySearch(arr, r[q] + 1, size + 1);
//            System.out.println("before " + l[q] + " " + r[q]);
//            System.out.println("after " + lo + " " + hi);
                tree.update(lo, hi - 1, op[q]);
                out.println(tree.query());
            }
        }

        private static int binarySearch(int[] a, int x, int n) {
            int lo = -1, hi = n;
            while (hi - lo > 1) {
                int m = lo + (hi - lo) / 2;
                if (a[m] < x) {
                    lo = m;
                } else {
                    hi = m;
                }
            }
            return hi;
        }

        private static void shuffle(int[] a) {
            for (int i = 0; i < a.length; ++i) {
                int idx = rnd.nextInt(a.length - i);
                int tmp = a[i];
                a[i] = a[idx];
                a[idx] = tmp;
            }
        }

        static class LazySegmentTree {
            int[] tree;
            int[] promise;
            int[] s;
            int n;

            public LazySegmentTree(int[] a) {
                this.n = a.length;
                s = new int[n];
                s[0] = a[0];
                for (int i = 1; i < n; ++i) {
                    s[i] = s[i - 1] + a[i];
                }
                int N = Integer.highestOneBit(Math.max(n, 1)) << 2;
                tree = new int[N];
                promise = new int[N];
                Arrays.fill(promise, -1);
                build(1, 0, n - 1, a);
            }

            private void build(int v, int tl, int tr, int[] a) {
                if (tl == tr) {
                    tree[v] = a[tl];
                    return;
                }
                int tm = (tl + tr) >>> 1;
                build(2 * v, tl, tm, a);
                build(2 * v + 1, tm + 1, tr, a);
                tree[v] = tree[2 * v] + tree[2 * v + 1];
            }

            private void push(int v, int tl, int tr) {
                if (promise[v] == -1) {
                    return;
                }
                promise[2 * v] = promise[2 * v + 1] = promise[v];
                int tm = (tl + tr) >>> 1;
                if (promise[v] == 0) {
                    tree[2 * v] = tree[2 * v + 1] = 0;
                } else {
                    tree[2 * v] = sum(tl, tm);
                    tree[2 * v + 1] = sum(tm + 1, tr);
                }
                promise[v] = -1;
            }

            public void update(int l, int r, int t) {
                update(1, 0, n - 1, l, r, t);
            }

            private void update(int v, int tl, int tr, int l, int r, int type) {
                if (l > r) return;
                if (tl == l && tr == r) {
                    if (type == 0) {
                        tree[v] = 0;
                    } else {
                        tree[v] = sum(l, r);
                    }
                    promise[v] = type;
                    return;
                }
                push(v, tl, tr);
                int tm = (tl + tr) >>> 1;
                update(2 * v, tl, tm, l, Math.min(tm, r), type);
                update(2 * v + 1, tm + 1, tr, Math.max(l, tm + 1), r, type);
                tree[v] = tree[2 * v] + tree[2 * v + 1];
            }

            public int query() {
                return tree[1];
            }

            private int sum(int l, int r) {
                int ret = s[r];
                if (l > 0) {
                    ret -= s[l - 1];
                }
                return ret;
            }

        }

    }

    static class QuickScanner {
        BufferedReader in;
        StringTokenizer token;
        String delim;

        public QuickScanner(InputStream inputStream) {
            this.in = new BufferedReader(new InputStreamReader(inputStream));
            this.delim = " \n\t";
            this.token = new StringTokenizer("", delim);
        }

        public QuickScanner(InputStream inputStream, String delim) {
            this.in = new BufferedReader(new InputStreamReader(inputStream));
            this.delim = delim;
            this.token = new StringTokenizer("", delim);
        }

        public boolean hasNext() {
            while (!token.hasMoreTokens()) {
                try {
                    String s = in.readLine();
                    if (s == null) return false;
                    token = new StringTokenizer(s, delim);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
            }
            return true;
        }

        public String next() {
            hasNext();
            return token.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

    }
}