Задача E. (20081222) Суммы без модуля

Автор:Пётр Митричев   Ограничение времени:3 сек
Входной файл:sum.in   Ограничение памяти:64 Мб
Выходной файл:sum.out  
Максимальный балл:100  

Условие

Участники сборов приезжают на сборы группами, и их необходимо заселить в гостиницу. Недолго думая, администратор гостиницы селит i-ю группу в комнаты с номерами с li по ri включительно, по одному человеку в комнату (соответственно, в i-й группе ri − li + 1 человек). Комнаты не резиновые, а именно вмещают лишь k − 1 человек. Как только в комнату заселяется k-й человек, все обитатели этой комнаты обижаются и уезжают домой (включая только что заселившегося).

Вдохновленный новым эффективным методом заселения, администратор решил применить подобный метод для завтраков, обедов и ужинов участников сборов. А именно, на j-й прием пищи приглашаются лишь участники из комнат с номерами с sj по tj включительно. Вам необходимо подсчитать, сколько порций нужно готовить на каждый прием пищи.

Формат входного файла

В первой строке записаны три натуральных числа — число комнат n (1 ≤ n ≤ 100 000), характеристика вместимости комнаты k (2 ≤ k ≤ 5), и количество произошедших на сборах событий m (1 ≤ m ≤ 100 000). В последующих m строках описаны сами произошедшие события в хронологическом порядке, по одному на строке.

Каждое событие описывается тремя целыми числами. Заезд очередной группы участников описывается как "1 l r", где l и r задают диапазон номеров комнат для заселения (1 ≤ l ≤ r ≤ n). Очередной прием пищи описывается как "2 s t", где s и t (1 ≤ s ≤ t ≤ n) задают диапазон номеров комнат, приглашенных в столовую.

Формат выходного файла

На каждый запрос второго вида выведите количество кушающих участников на отдельной строке.

Примеры тестов

Входной файл (sum.in) Выходной файл (sum.out)
1
3 3 9
1 1 3
1 1 2
1 1 1
2 1 3
2 1 2
1 1 3
1 3 3
2 1 3
2 1 2
3
2
1
1

0.137s 0.019s 13