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