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
def f0(ns, qs, ds):
    ns = ns[:]
    ans = []
    for op, ll, rr in qs:
        # print("f0(a)", ns)
        if op == 2:
            ans.append(sum(ns[ll - 1: rr]))
        else:
            for i in range(ll - 1, rr):
                ns[i] = ds[ns[i]]
        # print("f0(b)", ns)
    return ans


class SegTree:
    def __init__(self, arr, ds):
        self.n = len(arr) - 1
        m = len(arr) << 2
        self.sums = [0] * m
        self.flag = [0] * m
        self.ds = ds
        self.build_helper(1, 0, self.n, arr)
        self.cnt = 0

    def build_helper(self, xi, xl, xr, arr):
        if xl == xr:
            self.sums[xi] = arr[xl]
            self.flag[xi] = int(arr[xl] <= 2)
            return
        xm = (xl + xr) >> 1
        self.build_helper(xi << 1, xl, xm, arr)
        self.build_helper((xi << 1) | 1, xm + 1, xr, arr)
        self.pull_up(xi)

    def pull_up(self, xi):
        self.sums[xi] = self.sums[xi << 1] + self.sums[(xi << 1) | 1]
        self.flag[xi] = self.flag[xi << 1] & self.flag[(xi << 1) | 1]

    def dec(self, ll, rr):
        self.dec_helper(1, 0, self.n, ll, rr)

    def dec_helper(self, xi, xl, xr, ql, qr):
        # self.cnt += 1
        if xl == xr:
            self.sums[xi] = self.ds[self.sums[xi]]
            self.flag[xi] = int(self.sums[xi] <= 2)
            return
        if ql <= xl and xr <= qr and self.flag[xi]:
            return
        xm = (xl + xr) >> 1
        if ql <= xm and qr >= xl:
            self.dec_helper(xi << 1, xl, xm, ql, qr)
        if ql <= xr and qr > xm:
            self.dec_helper((xi << 1) | 1, xm + 1, xr, ql, qr)
        self.pull_up(xi)

    def query_sum(self, ll, rr):
        return self.query_sum_helper(1, 0, self.n, ll, rr)

    def query_sum_helper(self, xi, xl, xr, ql, qr):
        # self.cnt += 1
        if ql <= xl and xr <= qr:
            return self.sums[xi]
        xm = (xl + xr) >> 1
        ans = 0
        if ql <= xm and qr >= xl:
            ans += self.query_sum_helper(xi << 1, xl, xm, ql, qr)
        if ql <= xr and qr > xm:
            ans += self.query_sum_helper((xi << 1) | 1, xm + 1, xr, ql, qr)
        return ans


def f1(ns, qs, ds):
    seg = SegTree(ns, ds)
    ans = []
    for op, ll, rr in qs:
        ll -= 1
        rr -= 1
        # print("f1(a)", [seg.query_sum(i, i) for i, x in enumerate(ns)])
        if op == 2:
            # with tm.at("op==2"):
            ans.append(seg.query_sum(ll, rr))
        else:
            # with tm.at("op==1"):
            seg.dec(ll, rr)
        # print("f1(b)", [seg.query_sum(i, i) for i, x in enumerate(ns)])
    # print(seg.n + 1, seg.cnt, round(seg.cnt / (seg.n + 1), 1))
    return ans


def get_ds(n):
    ans = [2] * (n + 1)
    ans[1] = 1
    for i in range(2, n // 2 + 2):
        for j in range(i + i, n + 1, i):
            ans[j] += 1
    return ans


def test():
    import numpy as np
    for t in range(1):
        # print(t)
        n = np.random.randint(1, 10000)
        q = np.random.randint(5, 10000)

        n = 100000
        q = 100000
        m = 1000000

        ns = np.random.randint(1, m, n).tolist()
        ds = get_ds(max(ns))
        qs = []

        # ns = [4, 4, 1, 1, 2]
        # qs = [(2, 4, 5), (1, 4, 4), (2, 1, 2), (1, 2, 5), (2, 5, 5)]
        # ds = [2, 1, 2, 2, 3]

        for _ in range(q):
            op = np.random.randint(1, 2 + 1)
            li, ri = sorted(np.random.randint(1, n + 1, 2))
            qs.append((op, li, ri))
        # J.same([f0, f1], **{"ns": ns, "qs": qs, "ds": ds})
        J.same([f1], **{"ns": ns, "qs": qs, "ds": ds})
    tm.print()


# from utils.oj import J
# from utils.timer_utils import tm
# if __name__ == '__main__':
#     # test()
#     J.multi(test)
#     exit()

n, q = map(int, input().split())
# qs = [list(map(int, input().split())) for _ in range(q)]
ns = list(map(int, input().split()))
ds = get_ds(max(ns))
seg = SegTree(ns, ds)
for _ in range(q):
    op, ll, rr = list(map(int, input().split()))
    ll -= 1
    rr -= 1
    if op == 2:
        print(seg.query_sum(ll, rr))
    else:
        seg.dec(ll, rr)
