Let D(x) be the number of positive divisors of a positive integer x. For example, D(2) = 2 (2 is divisible by 1 and 2), D(6) = 4 (6 is divisible by 1, 2, 3 and 6).

You are given an array a of n integers. You have to process two types of queries:

REPLACE l r — for every $\text{[math]}$ replace a_i with D(a_i);
SUM l r — calculate $\text{[math]}$ .

Print the answer for each SUM query.

Input

The first line contains two integers n and m (1 ≤ n, m ≤ 3·10⁵) — the number of elements in the array and the number of queries to process, respectively.

The second line contains n integers a₁, a₂, ..., a_n (1 ≤ a_i ≤ 10⁶) — the elements of the array.

Then m lines follow, each containing 3 integers t_i, l_i, r_i denoting i-th query. If t_i = 1, then i-th query is REPLACE l_i r_i, otherwise it's SUM l_i r_i (1 ≤ t_i ≤ 2, 1 ≤ l_i ≤ r_i ≤ n).

There is at least one SUM query.

Output

For each SUM query print the answer to it.

SUM and REPLACE

Examples