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:
//package educational.round36;
import java.io.ByteArrayInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.InputMismatchException;

public class E {
	InputStream is;
	PrintWriter out;
	String INPUT = "";
	
	void solve()
	{
		int n = ni();
		int Q = ni();
		int[] as = new int[Q];
		int[] bs = new int[Q];
		int[] ks = new int[Q];
		for(int i = 0;i < Q;i++){
			as[i] = ni();
			bs[i] = ni();
			ks[i] = ni();
		}
		int[] xs = new int[2*Q+2];
		xs[2*Q] = 1;
		xs[2*Q+1] = n+1;
		
		int p = 0;
		for(int i = 0;i < Q;i++){
			xs[p++] = as[i];
			xs[p++] = bs[i]+1;
		}
		int[] imap = shrinkX(xs);
		p = 0;
		for(int i = 0;i < Q;i++){
			as[i] = xs[p++];
			bs[i] = xs[p++];
		}
		int[] vals = new int[imap.length];
		for(int i = 0;i < imap.length-1;i++){
			vals[i] = imap[i+1] - imap[i];
		}
		SegmentTreeOverwrite st = new SegmentTreeOverwrite(vals);
		for(int i = 0;i < Q;i++){
			st.update(as[i], bs[i], ks[i] - 1);
			out.println(st.sums[1]);
		}
	}
	
	public static class SegmentTreeOverwrite {
		public int M, H, N;
		public int[] sums;
		public int[] cover;
		public int[] cums;
		public int I = Integer.MAX_VALUE;
		
		public SegmentTreeOverwrite(int[] w)
		{
			N = w.length;
			
			M = Integer.highestOneBit(Math.max(N-1, 1))<<2;
			H = M>>>1;
			cover = new int[M];
			sums = new int[M];
			Arrays.fill(cover, I);
			for(int i = 0;i < N;i++){
				cover[H+i] = 1;
				sums[H+i] = w[i];
			}
			cums = new int[H+1];
			for(int i = 0;i < H;i++){
				cums[i+1] = cums[i] + (i < N ? w[i] : 0);
			}
			
			for(int i = H-1;i >= 1;i--){
				propagate(i);
			}
		}
		
		private void propagate(int i){
			if(cover[i] == I){
				sums[i] = sums[2*i] + sums[2*i+1];
			}else if(cover[i] == 1){
				int h = Integer.highestOneBit(i);
				int ind = i - h;
				int seg = H/h;
				sums[i] = cums[seg*(ind+1)] - cums[seg*ind];
			}else{
				sums[i] = 0;
			}
		}
		
		public void update(int l, int r, int v){ update(l, r, v, 0, H, 1); }
		
		private void update(int l, int r, int v, int cl, int cr, int cur)
		{
			if(l <= cl && cr <= r){
				cover[cur] = v;
				propagate(cur);
			}else{
				int mid = cl+cr>>>1;
				if(cover[cur] != I){ // back-propagate
					cover[2*cur] = cover[2*cur+1] = cover[cur];
					cover[cur] = I;
					propagate(2*cur);
					propagate(2*cur+1);
				}
				if(cl < r && l < mid){
					update(l, r, v, cl, mid, 2*cur);
				}
				if(mid < r && l < cr){
					update(l, r, v, mid, cr, 2*cur+1);
				}
				propagate(cur);
			}
		}
	}

	
	public static int[] shrinkX(int[] a) {
		int n = a.length;
		long[] b = new long[n];
		for (int i = 0; i < n; i++)
			b[i] = (long) a[i] << 32 | i;
		b = radixSort(b);
//		Arrays.sort(b);
		int[] ret = new int[n];
		int p = 0;
		ret[0] = (int) (b[0] >> 32);
		for (int i = 0; i < n; i++) {
			if (i > 0 && (b[i] ^ b[i - 1]) >> 32 != 0) {
				p++;
				ret[p] = (int) (b[i] >> 32);
			}
			a[(int) b[i]] = p;
		}
		return Arrays.copyOf(ret, p + 1);
	}
	
	public static long[] radixSort(long[] f){ return radixSort(f, f.length); }
	public static long[] radixSort(long[] f, int n)
	{
		long[] to = new long[n];
		{
			int[] b = new int[65537];
			for(int i = 0;i < n;i++)b[1+(int)(f[i]&0xffff)]++;
			for(int i = 1;i <= 65536;i++)b[i]+=b[i-1];
			for(int i = 0;i < n;i++)to[b[(int)(f[i]&0xffff)]++] = f[i];
			long[] d = f; f = to;to = d;
		}
		{
			int[] b = new int[65537];
			for(int i = 0;i < n;i++)b[1+(int)(f[i]>>>16&0xffff)]++;
			for(int i = 1;i <= 65536;i++)b[i]+=b[i-1];
			for(int i = 0;i < n;i++)to[b[(int)(f[i]>>>16&0xffff)]++] = f[i];
			long[] d = f; f = to;to = d;
		}
		{
			int[] b = new int[65537];
			for(int i = 0;i < n;i++)b[1+(int)(f[i]>>>32&0xffff)]++;
			for(int i = 1;i <= 65536;i++)b[i]+=b[i-1];
			for(int i = 0;i < n;i++)to[b[(int)(f[i]>>>32&0xffff)]++] = f[i];
			long[] d = f; f = to;to = d;
		}
		{
			int[] b = new int[65537];
			for(int i = 0;i < n;i++)b[1+(int)(f[i]>>>48&0xffff)]++;
			for(int i = 1;i <= 65536;i++)b[i]+=b[i-1];
			for(int i = 0;i < n;i++)to[b[(int)(f[i]>>>48&0xffff)]++] = f[i];
			long[] d = f; f = to;to = d;
		}
		return f;
	}


	
	void run() throws Exception
	{
//		StringBuilder sb = new StringBuilder();
//		Random gen = new Random(1000000009L);
//		int n = 1000000000;
//		int q = 300000;
//		sb.append(n + " ");
//		sb.append(q + " ");
//		for(int i = 0;i < q;i++){
//			int v1 = gen.nextInt(n);
//			int v2 = gen.nextInt(n);
//			sb.append(Math.min(v1, v2) + 1 + " ");
//			sb.append(Math.max(v1, v2) + 1 + " ");
//			sb.append(gen.nextInt(2) + 1 + "\n");
//		}
//		INPUT = sb.toString();
		
		is = oj ? System.in : new ByteArrayInputStream(INPUT.getBytes());
		out = new PrintWriter(System.out);
		
		long s = System.currentTimeMillis();
		solve();
		out.flush();
		tr(System.currentTimeMillis()-s+"ms");
	}
	
	public static void main(String[] args) throws Exception { new E().run(); }
	
	private byte[] inbuf = new byte[1024];
	public int lenbuf = 0, ptrbuf = 0;
	
	private int readByte()
	{
		if(lenbuf == -1)throw new InputMismatchException();
		if(ptrbuf >= lenbuf){
			ptrbuf = 0;
			try { lenbuf = is.read(inbuf); } catch (IOException e) { throw new InputMismatchException(); }
			if(lenbuf <= 0)return -1;
		}
		return inbuf[ptrbuf++];
	}
	
	private boolean isSpaceChar(int c) { return !(c >= 33 && c <= 126); }
	private int skip() { int b; while((b = readByte()) != -1 && isSpaceChar(b)); return b; }
	
	private double nd() { return Double.parseDouble(ns()); }
	private char nc() { return (char)skip(); }
	
	private String ns()
	{
		int b = skip();
		StringBuilder sb = new StringBuilder();
		while(!(isSpaceChar(b))){ // when nextLine, (isSpaceChar(b) && b != ' ')
			sb.appendCodePoint(b);
			b = readByte();
		}
		return sb.toString();
	}
	
	private char[] ns(int n)
	{
		char[] buf = new char[n];
		int b = skip(), p = 0;
		while(p < n && !(isSpaceChar(b))){
			buf[p++] = (char)b;
			b = readByte();
		}
		return n == p ? buf : Arrays.copyOf(buf, p);
	}
	
	private char[][] nm(int n, int m)
	{
		char[][] map = new char[n][];
		for(int i = 0;i < n;i++)map[i] = ns(m);
		return map;
	}
	
	private int[] na(int n)
	{
		int[] a = new int[n];
		for(int i = 0;i < n;i++)a[i] = ni();
		return a;
	}
	
	private int ni()
	{
		int num = 0, b;
		boolean minus = false;
		while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
		if(b == '-'){
			minus = true;
			b = readByte();
		}
		
		while(true){
			if(b >= '0' && b <= '9'){
				num = num * 10 + (b - '0');
			}else{
				return minus ? -num : num;
			}
			b = readByte();
		}
	}
	
	private long nl()
	{
		long num = 0;
		int b;
		boolean minus = false;
		while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
		if(b == '-'){
			minus = true;
			b = readByte();
		}
		
		while(true){
			if(b >= '0' && b <= '9'){
				num = num * 10 + (b - '0');
			}else{
				return minus ? -num : num;
			}
			b = readByte();
		}
	}
	
	private boolean oj = System.getProperty("ONLINE_JUDGE") != null;
	private void tr(Object... o) { if(!oj)System.out.println(Arrays.deepToString(o)); }
}