Суми без модуля
Участники зборів приїзжають на збори групами, і їх необхідно поселити у готель. Недовго думаючи, адміністратор готелю селить 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) задають діапазон номерів кімнат, запрошених у їдальню.
Вихідні дані
Для кожного запиту другого типу виведіть кільіксть участників, що їдять, у окремому рядку.