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