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:

1. REPLACE l r — for every replace a_i with D(a_i);
2. SUM l r — calculate .

Print the answer for each SUM query.

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.

For each SUM query print the answer to it.