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 sys

class FenwickTree(object):
    """Implementation of Fenwick Tree (a.k.a Binary Indexed Tree). [v1.0]

    This implentation uses 0-based indexing.
    """
    def __init__(self, n, lst=None):
        """Initialize Fenwick Tree for n elements. If lst is given, Fenwick
        Tree is initiailzed from the list in O(n) time.
        """
        if not lst:
            self._data = [0] * n
        else:
            self._data = lst
            for i in range(1, n + 1):
                j = i + (i & -i)
                if j <= n:
                    self._data[j - 1] += self._data[i - 1]

    def sum(self, beg, end):
        """Return the sum of elements in range [beg, end)."""
        if beg > 0:
            return self.sum(0, end) - self.sum(0, beg)
        s = 0
        while end > 0:
            s += self._data[end - 1]
            end -= end & -end
        return s

    def add(self, idx, val):
        """Add val to the element at idx."""
        idx += 1
        while idx <= len(self._data):
            self._data[idx - 1] += val
            idx += idx & -idx
            
def main():
    
    n, m = [int(x) for x in sys.stdin.readline().split()]
    a = [int(x) for x in sys.stdin.readline().split()]
    
    tr = FenwickTree(n, a[:])
    
    nm = 1000001
    tt = [2] * nm
    for i in range(2, 1001):
        for j in range(i+i, nm, i):
            tt[j] += 1
    tt[1]=1
    
    
    dd = {}
    for i in range(n):
        if tt[a[i]] < a[i]:
            dd[i] = a[i]
    #print(dd)
    
    for _ in range(m):
        c, l, r = [int(x) for x in sys.stdin.readline().split()]
        l -=1
        r-=1
        if c==2 :
            print(tr.sum(l, r+1))
        else:
            xx=[]
            for k,v in dd.items():
                if l<=k<=r:
                    nnn = tt[v]
                    tr.add(k, nnn - v)
                    xx.append((k, nnn))
            for aa,bb in xx:
                if bb<=2:
                    del dd[aa]
                else:
                    dd[aa] = bb
                        
                    
        
        
            
        
    
if __name__ == '__main__':
    main()
        