Участники сборов приезжают на сборы группами, и их необходимо заселить в гостиницу. Недолго думая, администратор гостиницы селит 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**" (1 ≤ l ≤ r ≤ n), где l и r задают диапазон номеров комнат для заселения. Очередной прием пищи описывается как "**2 s t**", где s и t (1 ≤ s ≤ t ≤ n) задают диапазон номеров комнат, приглашенных в столовую.

Выходные данные

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