В этом году Алексей окончил школу, и теперь он первокурсник Берляндского Государственного Университета. Для него стало неожиданностью, что, несмотря на специализацию программиста, ему все равно надо было посещать физкультуру! Конец семестра уже не за горами, а Алексей не посетил еще ни одной пары!
Разумеется Алексей не хочет вылететь, поэтому ему интересно узнать, сколько рабочих дней осталось до конца семестра, ведь только тогда он может посещать физкультуру. Но в БГУ подсчет количества рабочих дней — задача не из легких:
До конца семестра осталось n дней (пронумерованных от 1 до n), и все они изначально рабочие. Затем публикуются q приказов один за другим. Каждый приказ определяется тремя числами l, r и k:
Помогите Алексею посчитать количество рабочих дней до конца семестра после каждого приказа!
В первой строке записано целое число 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
Название |
---|