Автор: | Пётр Митричев | Ограничение времени: | 3 сек | |
Входной файл: | sum.in | Ограничение памяти: | 64 Мб | |
Выходной файл: | sum.out | |||
Максимальный балл: | 100 |
Участники сборов приезжают на сборы группами, и их необходимо заселить в гостиницу. Недолго думая, администратор гостиницы селит i-ю группу в комнаты с номерами с li по ri включительно, по одному человеку в комнату (соответственно, в i-й группе ri−li+1 человек). Комнаты не резиновые, а именно вмещают лишь k−1 человек. Как только в комнату заселяется k-й человек, все обитатели этой комнаты обижаются и уезжают домой (включая только что заселившегося).
Вдохновленный новым эффективным методом заселения, администратор решил применить подобный метод для завтраков, обедов и ужинов участников сборов. А именно, на j-й прием пищи приглашаются лишь участники из комнат с номерами с sj по tj включительно. Вам необходимо подсчитать, сколько порций нужно готовить на каждый прием пищи.
В первой строке записаны три натуральных числа — число комнат n (1≤n≤100000), характеристика вместимости комнаты k (2≤k≤5), и количество произошедших на сборах событий m (1≤m≤100000). В последующих m строках описаны сами произошедшие события в хронологическом порядке, по одному на строке.
Каждое событие описывается тремя целыми числами. Заезд очередной группы участников описывается как "1 l r", где l и r задают диапазон номеров комнат для заселения (1≤l≤r≤n). Очередной прием пищи описывается как "2 s t", где s и t (1≤s≤t≤n) задают диапазон номеров комнат, приглашенных в столовую.
На каждый запрос второго вида выведите количество кушающих участников на отдельной строке.
№ | Входной файл (sum.in ) |
Выходной файл (sum.out ) |
---|---|---|
1 |
|
|