# Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

# Chowdhury Saheb & the Numbers

You like short description of problems? Me too! Let’s go to an easy problem.

You are given an array of **N** integers. Let, every integer of the given array has an initial strength equal to its total number of divisors.

Let **X** is an integer, now, let’s define a function,

```
strength(X) = number of divisors of X
```

You will be given **Q** queries. In each query, you will need to perform any of these three types of category given below.

**1 X L R**

Let’s define a function,

```
Number_Giri(X, L, R) = strength(X) * number of occurrence of X between position L to R
```

Print the value of **Number_Giri(X, L, R)** in a single line.

**2 X Y**

Increase the strength of **X** by **Y**. But remember that, **strength of a number cannot be greater than that number.** That means strength(X) always should be less than or equal to X. So, if there will any overflow of the value of strength(X) then compute,

```
strength(X) = min(strength(X), X)
```

You need not to print anything here.

**3 X Y**

Decrease the strength of **X** by **Y**. But remember that, **strength of a number cannot be less than 1.** That means strength(X) always should be greater than or equal to 1. So, if there will any underflow of the value of strength(X) then compute,

```
strength(X) = max(strength(X), 1)
```

You need not to print anything here.

## Input

The input starts with two integers **N (1 ≤ N ≤ 10000)** and **Q (1 ≤ Q ≤ 10^6)** denoting the number of elements of the array and the total number of queries.

The second line consist of N integers **ar{i} (1 ≤ ar{i} ≤ 1000)** where **(1 ≤ i ≤ N)**.

The next **Q** lines contains any of three types of query described above.

## Output

For each query, perform the query as described above.

#### Constrains

1 ≤ N ≤ 100001 ≤ Q ≤ 10^6

1 ≤ X, every elements of array ≤ 1000

1 ≤ Y ≤ 10000

1 ≤ L ≤ R ≤ N

## Samples

Input | Output |
---|---|

4 5 1 3 1 3 1 1 1 4 2 3 1 1 3 2 4 3 3 5 1 3 1 2 | 2 6 1 |

Dataset is huge. Use faster I/O.