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
import io, os, sys

pypyin = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline
cpyin = sys.stdin.readline
input = pypyin if 'PyPy' in sys.version else cpyin

def strput():
    return input().decode() if 'PyPy' in sys.version else input()

# code starts here

class SegmentTree:
    tot = [] # interval sum
    val = [] # maximum value
    size = 0

    def __init__(self, n):
        self.tot = [0] * (n * 2)
        self.val = [0] * (n * 2)
        self.size = n

    def build(self, a):
        for i in range(self.size):
            self.tot[self.size + i] = a[i]
            self.val[self.size + i] = a[i]
        for i in range(self.size - 1, -1, -1):
            self.tot[i] = self.tot[i << 1] + self.tot[i << 1 | 1]
            self.val[i] = max(self.val[i << 1], self.val[i << 1 | 1])

    def modify(self, u, v, divcnt):
        for i in range(u, v):
            temp = self.tot[self.size + i]
            self.tot[self.size + i] = divcnt[temp]
            self.val[self.size + i] = divcnt[temp]
        for i in range(self.size - 1, -1, -1):
            self.tot[i] = self.tot[i << 1] + self.tot[i << 1 | 1]
            self.val[i] = max(self.val[i << 1], self.val[i << 1 | 1])
    
    def get_sum(self, u, v):
        u += self.size
        v += self.size
        res = 0
        while u < v:
            if u & 1:
                res += self.tot[u]
                u += 1
            if v & 1:
                res += self.tot[v - 1]
                v -= 1
            u >>= 1
            v >>= 1
        return res

    def get_max(self, u, v):
        u += self.size
        v += self.size
        res = -1
        while u < v:
            if u & 1:
                res = max(res, self.val[u])
                u += 1
            if v & 1:
                res = max(res, self.val[v - 1])
                v -= 1
            u >>= 1
            v >>= 1
        return res


def calc_divcnt():
    divcnt = [0] * 1000100
    for i in range(1, 1000100):
        for j in range(i, 1000100, i):
            divcnt[j] += 1
    return divcnt


def main():
    n, m = [int(x) for x in input().split()]
    a = [int(x) for x in input().split()]
    tree = SegmentTree(n)
    tree.build(a)
    divcnt = calc_divcnt()

    for i in range(m):
        t, l, r = [int(x) for x in input().split()]
        if t == 1:
            itv_max = tree.get_max(l - 1, r)
            if(itv_max > 2):
                tree.modify(l - 1, r, divcnt)
        if t == 2:
            print(tree.get_sum(l - 1, r))


if __name__ == "__main__":
    main()