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.*;
import java.util.*;
import java.lang.*;
import java.lang.reflect.Array;

public class Main {
	private static class MyScanner {
		BufferedReader br;
		StringTokenizer st;

		public MyScanner() {
			if (_DEBUG) {
				try {
					br = new BufferedReader(new FileReader("test.in"));
				} catch (Exception e) {
					e.printStackTrace();
					System.exit(1);;
				}
			} else {
				br = new BufferedReader(new InputStreamReader(System.in));				
			}
		}

		String next() {
			while (st == null || !st.hasMoreElements()) {
				try {
					st = new StringTokenizer(br.readLine());
				} catch (Exception e) {
					e.printStackTrace();
					return "";
				}
			}
			return st.nextToken();
		}

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

		long nextLong() {
			return Long.parseLong(next());
		}

		double nextDouble() {
			return Double.parseDouble(next());
		}

		String nextLine() {
			String str = "";
			try {
				str = br.readLine();
			} catch (IOException e) {
				e.printStackTrace();
			}
			return str;
		}
	}

	private static MyScanner scan = new MyScanner();
	private static final boolean _DEBUG = false;
	private static int debugCount = 0;
	private static final int MAXLINES = 200;
	
	private static void debug(String msg) {
		if (_DEBUG && debugCount < MAXLINES) {
			System.out.print(msg);
		}
	}
	
	private static void debugln(String msg) {
		if (_DEBUG && debugCount < MAXLINES) {
			System.out.println(msg);
			debugCount++;
		}
	}
	
	private static void debugln() {
		if (_DEBUG && debugCount < MAXLINES) {
			System.out.println();
			debugCount++;
		}
	}
	
	private static class SegmentTree {
		public int size;
		public int[] tree;
		public int[] lazy;
		public int[] lens;
		
		public SegmentTree(int size) {
			this.size = size;
			tree = new int[this.size*4];
			lazy = new int[tree.length];
			Arrays.fill(lazy, -1);
			lens = new int[size+1];
		}
		
		public void update(int value, int uLeft, int uRight) {
			update(value, uLeft, uRight, 1, 0, size-1);
		}
		
		public void update(int value, int uLeft, int uRight, int index, int left, int right) {
			if (uLeft <= uRight) {
				if (uLeft == left && uRight == right) {
					lazy[index] = value;
					if (value != 0) {
						tree[index] = lens[right+1] - lens[left];
					} else {
						tree[index] = 0;
					}
				} else {
					int mid = (left + right) >> 1;
					int newIndex = index << 1;
					if (lazy[index] != -1) {
						lazy[newIndex] = lazy[index];
						lazy[newIndex+1] = lazy[index];
						if (lazy[index] != 0) {
							tree[newIndex] = (lens[mid+1] - lens[left]);
							tree[newIndex+1] = (lens[right+1] - lens[mid+1]);
						} else {
							tree[newIndex] = 0;
							tree[newIndex+1] = 0;
						}
						lazy[index] = -1;
					}
					update(value, uLeft, Math.min(uRight, mid), newIndex, left, mid);
					update(value, Math.max(uLeft, mid+1), uRight, newIndex+1, mid+1, right);
					tree[index] = tree[newIndex] + tree[newIndex+1];
				}
//				System.out.println(left+" "+right+" "+tree[index]);
			}
		}
		
		public int query(int qLeft, int qRight) {
			return query(qLeft, qRight, 1, 0, size-1);
		}
		
		public int query(int qLeft, int qRight, int index, int left, int right) {
			if (qRight < qLeft) {
				return 0;
			} else if (qLeft == left && qRight == right) {
				return tree[index];
			} else {
				int mid = (left + right) >> 1;
				int newIndex = index << 1;
				if (lazy[index] != -1) {
					lazy[newIndex] = lazy[index];
					lazy[newIndex+1] = lazy[index];
					if (lazy[index] != 0) {
						tree[newIndex] = (lens[mid+1] - lens[left]);
						tree[newIndex+1] = (lens[right+1] - lens[mid+1]);
					} else {
						tree[newIndex] = 0;
						tree[newIndex+1] = 0;
					}
					lazy[index] = -1;
				}
				return query(qLeft, Math.min(qRight, mid), newIndex, left, mid) + 
					   query(Math.max(qLeft, mid+1), qRight, newIndex+1, mid+1, right);
			}
		}
	}
	
	private static class Node implements Comparable<Node> {
		public int value;
		public int index;
		public Node next;
		
		public Node(int value) {
			this.value = value;
			index = -1;
			next = null;
		}
		
		public int compareTo(Node o) {
			return this.value - o.value;
		}
	}
	
	private static PrintWriter out;
	
    public static void main(String args[]) throws java.lang.Exception {
        Main inst = new Main();
        out = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
        inst.excute();
        out.close();
    }
    
    private void excute() {
    	int N = scan.nextInt();
    	int Q = scan.nextInt();
    	Node[] nodes = new Node[Q*2+2];
    	Node[] queries = new Node[Q*2];
    	int[] set = new int[Q];
    	nodes[0] = new Node(1);
    	nodes[Q*2+1] = new Node(N+1);
    	for (int i = 0; i < Q; i++) {
    		queries[i*2] = nodes[i*2+1] = new Node(scan.nextInt());
    		queries[i*2+1] = nodes[i*2+2] = new Node(scan.nextInt()+1);
    		set[i] = scan.nextInt()-1;
    	}
    	Arrays.sort(nodes);
    	nodes[0].index = 0;
    	Node prev = nodes[0];
    	int index = 0;
    	for (int i = 1; i < nodes.length; i++) {
    		if (nodes[i].value > prev.value) {
    			index++;
    			prev.next = nodes[i];
    			prev = nodes[i];
    		}
			nodes[i].index = index;
    	}
    	SegmentTree tree = new SegmentTree(index);
    	Node curNode = nodes[0];
    	while (curNode.next != null) {
    		tree.lens[curNode.index+1] = tree.lens[curNode.index] + curNode.next.value - curNode.value;
    		curNode = curNode.next;
    	}
//    	System.out.println(Arrays.toString(tree.lens));
    	tree.update(1, 0, tree.size-1);
    	for (int i = 0; i < Q; i++) {
    		int left = queries[i*2].index;
    		int right = queries[i*2+1].index;
//    		System.out.println(left+" "+right);
    		tree.update(set[i], left, right-1);
    		out.println(tree.tree[1]);
    	}
    }
}