Sums without a module
Participants attending a meeting arrive in groups and need to be accommodated in a hotel. The hotel administrator assigns the i-th group to rooms numbered from l[i] to r[i] inclusive, with one person per room. Thus, the i-th group consists of r[i] - l[i] + 1 people. However, the rooms have a strict capacity limit: they can only hold up to k - 1 people. If a k-th person is placed in a room, all occupants, including the new arrival, become upset and leave.
Inspired by this unique method of managing room assignments, the administrator decided to implement a similar approach for organizing meals—breakfasts, lunches, and dinners—for the meeting participants. Specifically, only participants from rooms numbered from s[j] to t[j] inclusive are invited to the j-th meal. Your task is to determine how many portions need to be prepared for each meal.
Input
The first line contains three natural numbers: the number of rooms n (1 ≤ n ≤ 100000), the room capacity limit k (2 ≤ k ≤ 5), and the number of events m (1 ≤ m ≤ 100000) that occurred during the meeting. The following m lines describe these events in chronological order, one per line. Each event is represented by three integers. The arrival of a new group of participants is described as "1 l r" (1 ≤ l ≤ r ≤ n), where l and r specify the range of room numbers for accommodation. A meal event is described as "2 s t", where s and t (1 ≤ s ≤ t ≤ n) define the range of room numbers invited to the meal.
Output
For each meal event, output the number of participants who will be eating, each on a separate line.