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.

Sample

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.