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 <img align="middle" class="tex-formula" src="https://espresso.codeforces.com/6afb5e3d414ffbb040c175e23c6627da949add06.png" style="max-width: 100.0%;max-height: 100.0%;"/> replace *a*<sub class="lower-index">*i*</sub> with *D*(*a*<sub class="lower-index">*i*</sub>); 1.  SUM *l* *r* — calculate <img align="middle" class="tex-formula" src="https://espresso.codeforces.com/1e50b9417bb7e50d92d43134922596e938249431.png" style="max-width: 100.0%;max-height: 100.0%;"/>. 
Print the answer for each SUM query.
The first line contains two integers *n* and *m* (1 ≤ *n*, *m* ≤ 3·10<sup class="upper-index">5</sup>) — the number of elements in the array and the number of queries to process, respectively.

The second line contains *n* integers *a*<sub class="lower-index">1</sub>, *a*<sub class="lower-index">2</sub>, ..., *a*<sub class="lower-index">*n*</sub> (1 ≤ *a*<sub class="lower-index">*i*</sub> ≤ 10<sup class="upper-index">6</sup>) — the elements of the array.

Then *m* lines follow, each containing 3 integers *t*<sub class="lower-index">*i*</sub>, *l*<sub class="lower-index">*i*</sub>, *r*<sub class="lower-index">*i*</sub> denoting *i*-th query. If *t*<sub class="lower-index">*i*</sub> = 1, then *i*-th query is REPLACE *l*<sub class="lower-index">*i*</sub> *r*<sub class="lower-index">*i*</sub>, otherwise it's SUM *l*<sub class="lower-index">*i*</sub> *r*<sub class="lower-index">*i*</sub> (1 ≤ *t*<sub class="lower-index">*i*</sub> ≤ 2, 1 ≤ *l*<sub class="lower-index">*i*</sub> ≤ *r*<sub class="lower-index">*i*</sub> ≤ *n*).

There is at least one SUM query.
none
7 6
6 4 1 10 3 2 4
2 1 7
2 4 5
1 3 5
2 4 4
1 5 7
2 1 7
30
13
4
22
4 2
1 1 1 3
1 1 4
2 1 4
5
10 2
1 1 1 1 1 1 1 1 1 9
1 1 10
2 1 10
12
4 2
1 1 3 1
1 1 4
2 1 4
5
5 3
1 1 1 1 3
2 1 5
1 1 5
2 1 5
7
6
7 10
1 1 1 1 1 1 1
1 1 7
1 1 7
1 1 7
1 1 7
1 1 7
1 1 7
1 1 7
1 1 7
1 1 7
2 1 7
7
from sys import stdin
import collections, heapq, bisect, math
 
input = stdin.readline
 
def rint():
    return int(input())
def rstr():
    return input().strip()
def rlstr():
    return list(input().strip().split())
def rlint():
    return list(map(int, input().split()))

def seive() :
    n = 10**6 + 1
    prime = [0]*n

    for i in range(2 , n) :
        if prime[i] == 0 :
            prime[i] = i 
            for j in range(i*i , n , i) :
                if prime[j] == 0 :
                    prime[j] = i

    return prime

prime = seive()

def D(x) :
    res = 1

    while x > 1 :
        div = prime[x]
        a = 1

        while div == prime[x] :
            x = x // div
            a += 1

        res *= a

    return res

def main():
    n , m = rlint()
    a = rlint()
    tree = [0]*(2*n + 1)

    for i in range(n) :
        tree[i + n] = a[i]

    for i in range(n - 1 , 0 , -1) :
        tree[i] = tree[2*i] + tree[2*i + 1]

    for _ in range(m) :
        t , l , r = rlint()
        l = l + n - 1
        r = r + n - 1

        if t == 1 :
            for k in range(l , r + 1) :
                tree[k] = D(tree[k])
                k //= 2

                while k > 0 :
                    tree[k] = tree[2*k] + tree[2*k + 1]
                    k //= 2

        else :
            res = 0 

            while l <= r :
                if l % 2 == 1 :
                    res += tree[l]
                    l += 1

                if r % 2 == 0 :
                    res += tree[r]
                    r -= 1

                l //= 2
                r //= 2

            print(res)

if __name__ == "__main__":
    main()