E. Занятия физкультуры
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В этом году Алексей окончил школу, и теперь он первокурсник Берляндского Государственного Университета. Для него стало неожиданностью, что, несмотря на специализацию программиста, ему все равно надо было посещать физкультуру! Конец семестра уже не за горами, а Алексей не посетил еще ни одной пары!

Разумеется Алексей не хочет вылететь, поэтому ему интересно узнать, сколько рабочих дней осталось до конца семестра, ведь только тогда он может посещать физкультуру. Но в БГУ подсчет количества рабочих дней — задача не из легких:

До конца семестра осталось n дней (пронумерованных от 1 до n), и все они изначально рабочие. Затем публикуются q приказов один за другим. Каждый приказ определяется тремя числами l, r и k:

  • Если k = 1, то все дни с l по r (включительно) становятся выходными. Если некоторые дни до этого были объявлены рабочими, то они все равно становятся выходными;
  • Если k = 2, то все дни с l по r (включительно) становятся рабочими. Если некоторые дни до этого были объявлены выходными, то они все равно становятся рабочими.

Помогите Алексею посчитать количество рабочих дней до конца семестра после каждого приказа!

Входные данные

В первой строке записано целое число n, а во второй — целое число q (1 ≤ n ≤ 109, 1 ≤ q ≤ 3·105) — количество дней до окончания семестра и количество приказов, соответственно.

Затем идут q строк, в i записаны три целых числа li, ri и ki, описывающие i-й запрос (1 ≤ li ≤ ri ≤ n, 1 ≤ ki ≤ 2).

Выходные данные

Выведите q целых чисел. i-е должно равняться количеству рабочих дней, оставшихся до конца семестра, после того, как опубликованы первые i приказов.

Пример
Входные данные
4
6
1 2 1
3 4 1
2 3 2
1 3 2
2 4 1
1 4 2
Выходные данные
2
0
2
3
1
4