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:
/*
Keep solving problems.
*/

import java.util.*;
import java.io.*;

public class CFA {
    BufferedReader br;
    PrintWriter out;
    StringTokenizer st;
    boolean eof;
    final long MOD = 1000L * 1000L * 1000L + 7;
    int[] dx = {0, -1, 0, 1};
    int[] dy = {1, 0, -1, 0};
    private static final String yes = "YES";
    private static final String no = "NO";

    class Pair implements Comparable<Pair> {
        int x;
        int y;
        public Pair(int x, int y) {
            this.x = x;
            this.y = y;
        }

        @Override
        public int compareTo(Pair o) {
            return Integer.compare(y, o.y);
        }

        @Override
        public int hashCode() {
            int res = 13;
            res = 37 * res + x;
            res = 37 * res + y;
            return res;
        }

        @Override
        public boolean equals(Object obj) {
            if(obj == null) {
                return false;
            }
            if(!(obj instanceof Pair)) {
                return false;
            }
            Pair o = (Pair) obj;
            return this.x == o.x && this.y == o.y;
        }
        @Override
        public String toString() {
            return "x: " + x + "; y: " + y;
        }
    }
    void solve() throws IOException {
        int n = nextInt();
        int q = nextInt();
        int res = n;
        TreeSet<Pair> ts = new TreeSet<>();
        for (int i = 0; i < q; i++) {
            int l = nextInt();
            int r = nextInt();
            int k = nextInt();
            if (k == 1) {
                SortedSet<Pair> set = ts.tailSet(new Pair(0, l));
                int min = l;
                int max = r;
                List<Pair> del = new ArrayList<>();
                for (Pair p : set) {
                    if (p.x <= r) {
                        del.add(p);
                        min = Math.min(min, p.x);
                        max = Math.max(max, p.y);
                        res += p.y - p.x + 1;
                    }
                    else {
                        break;
                    }
                }

                res -= max - min + 1;
                for (Pair p : del) {
                    ts.remove(p);
                }

                ts.add(new Pair(min, max));
            }
            else {
                SortedSet<Pair> set = ts.tailSet(new Pair(0, l));
                int min = l;
                int max = r;
                List<Pair> del = new ArrayList<>();
                for (Pair p : set) {
                    if (p.x <= r) {
                        del.add(p);
                        min = Math.min(min, p.x);
                        max = Math.max(max, p.y);

                        int left = Math.max(l, p.x);
                        int right = Math.min(r, p.y);
                        if (left <= right) {
                            res += right - left + 1;
                        }
                    }
                    else {
                        break;
                    }
                }

                for (Pair p : del) {
                    ts.remove(p);
                }

                if (l > min) {
                    ts.add(new Pair(min, l - 1));
                }

                if (r < max) {
                    ts.add(new Pair(r + 1, max));
                }
            }

            outln(res);
        }
    }

    void shuffle(int[] a) {
        int n = a.length;
        for(int i = 0; i < n; i++) {
            int r = i + (int) (Math.random() * (n - i));
            int tmp = a[i];
            a[i] = a[r];
            a[r] = tmp;
        }
    }

    int gcd(int a, int b) {
        while(a != 0 && b != 0) {
            int c = b;
            b = a % b;
            a = c;
        }
        return a + b;
    }

    private void outln(Object o) {
        out.println(o);
    }
    private void out(Object o) {
        out.print(o);
    }
    public CFA() throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        out = new PrintWriter(System.out);
        solve();
        out.close();
    }
    public static void main(String[] args) throws IOException {
        new CFA();
    }

    public long[] nextLongArr(int n) throws IOException{
        long[] res = new long[n];
        for(int i = 0; i < n; i++)
            res[i] = nextLong();
        return res;
    }
    public int[] nextIntArr(int n) throws IOException {
        int[] res = new int[n];
        for(int i = 0; i < n; i++)
            res[i] = nextInt();
        return res;
    }
    public String nextToken() {
        while (st == null || !st.hasMoreTokens()) {
            try {
                st = new StringTokenizer(br.readLine());
            } catch (Exception e) {
                eof = true;
                return null;
            }
        }
        return st.nextToken();
    }
    public String nextString() {
        try {
            return br.readLine();
        } catch (IOException e) {
            eof = true;
            return null;
        }
    }
    public int nextInt() throws IOException {
        return Integer.parseInt(nextToken());
    }
    public long nextLong() throws IOException {
        return Long.parseLong(nextToken());
    }
    public double nextDouble() throws IOException {
        return Double.parseDouble(nextToken());
    }
}