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

Условие

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

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

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

В первой строке записаны три натуральных числа — число комнат 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) задают диапазон номеров комнат, приглашенных в столовую.

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

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

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

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