Uolevi recently got a job as a kangaroo keeper. Unfortunately, some of his kangaroos immediately escaped, and Uolevi is in pursuit.

The kangaroo farm has m different kinds of kangaroos, where the i'th type of kangaroo moves exactly i meters per jump. To find the escaped kangaroos, Uolevi wants to calculate the amount of kangaroo footprints in the interval [a, b] of the road. When a kangaroo of type i escapes, it leaves a footprint at positions xi along the road, where x > 0 is a positive integer.

There are two kinds of events that can happen:

• A kangaroo of type i escapes, leaving footprints at positions i, 2i, and so on
• Uolevi counts the number of footprints in the interval [a, b].

Can you find the number of footprints Uolevi counts on each interval?

Input

The first line of input contains three integers n, m and q: the length of the road, the amount of kangaroo types, and the number of events.

After this, q lines follow, each of one of the two following types:

• 1 j: A kangaroo of type j escapes, leaving footprints at positions xj, where x > 0 is a positive integer
• 2 a b: Uolevi counts the amount of footprints in the interval [a, b]

Output

Print k lines where k is the amount of queries of type 2. On every such line, print the amount of footprints on the interval.

Constraints

• 1 \leq n, m, q \leq 10^{5}
• 1 \leq j \leq m
• 1 \leq a \leq b \leq n

Example

Input:

5 5 5
1 1
1 3
2 2 4
1 2
2 4 5

Output:

4
3