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.*;

public class D implements Runnable{
	public static void main (String[] args) {new Thread(null, new D(), "_cf", 1 << 28).start();}

	int n, oo = (int)2e9, res;
	TreeSet<Pair> set;
	
	public void run() {
		JoltyScanner js = new JoltyScanner(System.in);
		PrintWriter out = new PrintWriter(System.out);

		n = js.nextInt();
		int q = js.nextInt();
		
		set = new TreeSet<>();
		set.add(new Pair(1, n));
		
		res = n;
		for(int qq = 0; qq < q; qq++) {
			int l = js.nextInt();
			int r = js.nextInt();
			int k = js.nextInt();
			update(l, r, k == 2);

			if(k == 2) {
				//we've removed everything in this range so lets add it in
				//and update the answer properly
				res += r - l + 1;
				set.add(new Pair(l, r));
			}
			
			out.println(res);
		}
		
		
		out.close();
	}
	
	void update (int left, int right, boolean revive) {
		//find ranges whose left points are less than my right point
		Pair below, check = new Pair(right, oo);
		//while this range is existent and intersecting left and right
		while((below = set.floor(check)) != null && !(below.r < left)) {
			//get rid of this entire range
			res -= below.r - below.l + 1;
			set.remove(below);
			//update answer for trailing intersections
			if(below.r > right) {
				//over the right side
				//add back in the overcount
				set.add(new Pair(right+1, below.r));
				res += below.r - right;
			}
			if(below.l < left) {
				//over the left side
				//add back in the overcount
				set.add(new Pair(below.l, left-1));
				res += left - below.l;
			}
		}
	}
	
	class Pair implements Comparable<Pair> {
		int l, r;
		Pair (int a, int b) {
			l = a; r = b;
		}
		public int compareTo (Pair o ) {
			return Integer.compare(l, o.l);
		}
		public String toString() {
			return "[" + l + ", " + r + "]";
		}
	}
	
/*
General
 
7 10
1 5 1
2 4 1
3 3 1
4 4 2
2 2 2
6 7 1
5 6 2
1 6 2
1 7 1
7 7 2

Disjoint Check

10 9
1 3 1
4 6 2
4 10 2
5 9 2
5 7 1
8 8 2
4 4 2
10 10 1
9 9 2

Single Range Death Check

10 7
2 9 1
2 2 1
3 3 1
4 6 1
7 7 1
8 8 1
9 9 1

Single Range Health Check

10 3
2 9 1
3 6 2
2 2 2

Big Case

1000000000 5
1 1000000000 1
2 999999999 2
3 999999998 1
4 999999997 2
5 999999996 1

Removing Trailing Ranges Check

10 5
3 8 1
1 4 2
7 9 2
4 8 1
5 5 2

*/

	class JoltyScanner {
		public static final int BUFFER_SIZE = 1 << 16;
		public static final char NULL_CHAR = (char) -1;
		byte[] buffer = new byte[BUFFER_SIZE];
		int bufferIdx = 0, size = 0;
		char c = NULL_CHAR;
		BufferedInputStream in;
		public JoltyScanner(InputStream in) 
		{
			this.in = new BufferedInputStream(in, BUFFER_SIZE);
			c = nextChar();
		}
		public int nextInt() 
		{
			while(c < '0' || c > '9')
				c = nextChar();
			int res = 0;
			while(c >= '0' && c <= '9') {
				res = (res << 3) + (res << 1) + c - '0';
				c = nextChar();
			}
			return res;
		}
		public char nextChar() 
		{
			while (bufferIdx == size) 
			{
				try 
				{
					size = in.read(buffer);
				} catch (Exception e) 
				{
					return NULL_CHAR;
				}
				bufferIdx = 0;
			}
			return (char) buffer[bufferIdx++];
		}
	}

}