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

Вихідні дані

Для кожного запиту другого типу виведіть кільіксть участників, що їдять, у окремому рядку.