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.util.*;
import java.io.*;
import java.math.BigInteger;
 
public class Main
{
 
    static int mod = (int) (1e9+7);
    static InputReader in;
    static PrintWriter out;
    
    public static void main(String[] args)
    {
        in = new InputReader(System.in);
        out = new PrintWriter(System.out);            
        
        int n = in.nextInt();
        int q = in.nextInt();
        TreeMap<Integer,Integer> map = new TreeMap<>();
        map.put(1, n);

        long ans = n;
        while(q-- > 0){
            int l = in.nextInt();
            int r = in.nextInt();
            int k = in.nextInt();
            //debug(map);
            if(k == 1){
                int max = r;
                while(map.ceilingKey(l) != null){
                    int key = map.ceilingKey(l);
                    if(key > r) break;
                    ans -= map.get(key) - key + 1;
                    max = Math.max(max, map.get(key));
                    map.remove(key);
                }
                //debug(max,r);
                if(max > r){
                    if(map.containsKey(r + 1)) max = Math.max(max, map.get(r + 1));
                    ans += max - r;
                    map.put(r + 1, max);
                }
                int min = l;
                while(map.floorKey(l) != null){
                    int key = map.floorKey(l);
                    if(map.get(key) < l) break;
                    if(map.get(key) > r){
                        ans += map.get(key) - r;
                        map.put(r + 1, map.get(key));
                    }
                    ans -= map.get(key) - key + 1;
                    min = Math.min(min, key);
                    map.remove(key);
                }
                if(min < l){
                    ans += l - min;
                    map.put(min, l - 1);
                }
                //debug(map);
            }
            else{
                int max = r;
                while(map.higherKey(l) != null){
                    int key = map.higherKey(l);
                    if(key > r) break;
                    ans -= map.get(key) - key + 1;
                    max = Math.max(max, map.get(key));
                    map.remove(key);
                }
                int min = l;
                while(map.floorKey(l) != null){
                    int key = map.floorKey(l);
                    if(map.get(key) < l) break;
                    if(map.get(key) > r){
                        ans += map.get(key) - r;
                        map.put(r + 1, map.get(key));
                    }
                    ans -= map.get(key) - key + 1;
                    min = Math.min(min, key);
                    map.remove(key);
                }
                map.put(min, max);
                ans += max - min + 1;
            }
            //debug(map);
            out.println(ans);
        }
        
        out.close();
        
    }
 
    static class Pair implements Comparable<Pair>
    {
 
        int x,y;
        int i;
 
 
        Pair (int x,int y)
        {
                this.x = x;
                this.y = y;
        }
 
        Pair (int x,int y, int i)
        {
                this.x = x;
                this.y = y;
                this.i = i;
        }
 
        public int compareTo(Pair o)
        {
            if(this.x != o.x)
                return -Integer.compare(this.x, o.y);
            return -Integer.compare(this.y,o.y);
                //return 0;
        }
 
        public boolean equals(Object o)
        {
            if (o instanceof Pair)
            {
                Pair p = (Pair)o;
                return p.x == x && p.y==y;
            }
            return false;
        }
 
        @Override
        public String toString()
        {
            return x + " "+ y + " "+i;
        }
 
        /*public int hashCode()
        {
            return new Long(x).hashCode() * 31 + new Long(y).hashCode();
        }*/
 
    } 
 
    static long add(long a,long b){
        long x=(a+b);
        while(x>=mod) x-=mod;
        return x;
    }
 
    static long sub(long a,long b){
        long x=(a-b);
        while(x<0) x+=mod;
        return x;
    }
    
    static long mul(long a,long b){
        long x=(a*b);
        while(x>=mod) x-=mod;
        return x;
    }
    
    static String rev(String s){
        StringBuilder sb=new StringBuilder(s);
        sb.reverse();
        return sb.toString();
    }
    
    static long gcd(long x,long y)
    {
        if(y==0)
                return x;
        else
                return gcd(y,x%y);
    }
 
    static int gcd(int x,int y)
    {
        if(y==0)
                return x;
        else 
                return gcd(y,x%y);
    }
 
    static long pow(long n,long p,long m)
    {
         long  result = 1;
          if(p==0){
            return n;
          }
          
        while(p!=0)
        {
            if(p%2==1)
                result *= n;
            if(result >= m)
               result %= m;
            p >>=1;
            n*=n;
            if(n >= m)
                n%=m;
        }
        
        return result;
    }
 
    static long pow(long n,long p)
    {
        long  result = 1;
          if(p==0)
            return 1;
 
        while(p!=0)
        {
            if(p%2==1)
                result *= n;	    
            p >>=1;
            n*=n;	    
        }
        return result;
    }
 
    static void debug(Object... o)
    {
            System.out.println(Arrays.deepToString(o));
    }
 
    static class InputReader
    {
 
        private final InputStream stream;
        private final byte[] buf = new byte[8192];
        private int curChar, snumChars;
        private SpaceCharFilter filter;
 
        public InputReader(InputStream stream)
        {
                this.stream = stream;
        }
 
        public int snext()
        {
                if (snumChars == -1)
                        throw new InputMismatchException();
                if (curChar >= snumChars)
                {
                        curChar = 0;
                        try
                        {
                                snumChars = stream.read(buf);
                        } catch (IOException e)
                        {
                                throw new InputMismatchException();
                        }
                        if (snumChars <= 0)
                                return -1;
                }
                return buf[curChar++];
        }
 
        public int nextInt()
        {
                int c = snext();
                while (isSpaceChar(c))
                {
                        c = snext();
                }
                int sgn = 1;
                if (c == '-')
                {
                        sgn = -1;
                        c = snext();
                }
                int res = 0;
                do
                {
                        if (c < '0' || c > '9')
                                throw new InputMismatchException();
                        res *= 10;
                        res += c - '0';
                        c = snext();
                } while (!isSpaceChar(c));
                return res * sgn;
        }
 
        public long nextLong()
        {
                int c = snext();
                while (isSpaceChar(c))
                {
                        c = snext();
                }
                int sgn = 1;
                if (c == '-')
                {
                        sgn = -1;
                        c = snext();
                }
                long res = 0;
                do
                {
                        if (c < '0' || c > '9')
                                throw new InputMismatchException();
                        res *= 10;
                        res += c - '0';
                        c = snext();
                } while (!isSpaceChar(c));
                return res * sgn;
        }
 
        public int[] nextIntArray(int n)
        {
                int a[] = new int[n];
                for (int i = 0; i < n; i++)
                {
                        a[i] = nextInt();
                }
                return a;
        }
 
        public long[] nextLongArray(int n)
        {
                long a[] = new long[n];
                for (int i = 0; i < n; i++)
                {
                        a[i] = nextLong();
                }
                return a;
        }
 
        public String readString()
        {
                int c = snext();
                while (isSpaceChar(c))
                {
                        c = snext();
                }
                StringBuilder res = new StringBuilder();
                do
                {
                        res.appendCodePoint(c);
                        c = snext();
                } while (!isSpaceChar(c));
                return res.toString();
        }
 
        public String nextLine()
        {
                int c = snext();
                while (isSpaceChar(c))
                        c = snext();
                StringBuilder res = new StringBuilder();
                do
                {
                        res.appendCodePoint(c);
                        c = snext();
                } while (!isEndOfLine(c));
                return res.toString();
        }
 
        public boolean isSpaceChar(int c)
        {
                if (filter != null)
                        return filter.isSpaceChar(c);
                return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }
 
        private boolean isEndOfLine(int c)
        {
                return c == '\n' || c == '\r' || c == -1;
        }
 
        public interface SpaceCharFilter
        {
                public boolean isSpaceChar(int ch);
        }
 
    }
}