Суммы без модуля
Участники сборов приезжают на сборы группами, и их необходимо заселить в гостиницу. Недолго думая, администратор гостиницы селит i-ую группу в комнаты с номерами с l[i] по r[i] включительно, по одному человеку в комнату (соответственно, в i-ой группе r[i] - l[i] + 1 человек). Комнаты не резиновые, а именно вмещают лишь k - 1 человек. Как только в комнату заселяется k-ый человек, все обитатели этой комнаты обижаются и уезжают домой (включая только что заселившегося).
Вдохновленный новым эффективным методом заселения, администратор решил применить подобный метод для завтраков, обедов и ужинов участников сборов. А именно, на j-ый прием пищи приглашаются лишь участники из комнат с номерами с s[j] по t[j] включительно. Вам необходимо подсчитать, сколько порций нужно готовить на каждый прием пищи.
Входные данные
В первой строке записаны три натуральных числа - число комнат n (1 ≤ n ≤ 100000), характеристика вместимости комнаты k (2 ≤ k ≤ 5), и количество произошедших на сборах событий m (1 ≤ m ≤ 100000). В последующих m строках описаны сами произошедшие события в хронологическом порядке, по одному в строке. Каждое событие описывается тремя целыми числами. Заезд очередной группы участников описывается как "1 l r" (1 ≤ l ≤ r ≤ n), где l и r задают диапазон номеров комнат для заселения. Очередной прием пищи описывается как "2 s t", где s и t (1 ≤ s ≤ t ≤ n) задают диапазон номеров комнат, приглашенных в столовую.
Выходные данные
На каждый запрос второго вида выведите количество кушающих участников в отдельной строке.