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
#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 5, M = 1e6 + 5;
int arr[N], sums[N << 2], flag[N << 2], ds[M], n = 0;

void pull_up(int xi) {
    sums[xi] = sums[xi << 1] + sums[(xi << 1) | 1];
    flag[xi] = flag[xi << 1] & flag[(xi << 1) | 1];
}

void build_helper(int xi, int xl, int xr) {
    if (xl == xr) {
        sums[xi] = arr[xl];
        flag[xi] = (sums[xi] <= 2);
        return;
    }
    int xm = (xl + xr) >> 1;
    build_helper(xi << 1, xl, xm);
    build_helper((xi << 1) | 1, xm + 1, xr);
    pull_up(xi);
}

void dec_helper(int xi, int xl, int xr, int ql, int qr) {
    if (xl == xr) {
        sums[xi] = ds[sums[xi]];
        flag[xi] = (sums[xi] <= 2);
        return;
    }
    if (ql <= xl && xr <= qr and flag[xi]) {
        return;
    }
    int xm = (xl + xr) >> 1;
    if (ql <= xm && qr >= xl)
        dec_helper(xi << 1, xl, xm, ql, qr);
    if (ql <= xr && qr > xm)
        dec_helper((xi << 1) | 1, xm + 1, xr, ql, qr);
    pull_up(xi);
}

void dec(int ll, int rr) {
    dec_helper(1, 0, n - 1, ll, rr);
}

int query_sum_helper(int xi, int xl, int xr, int ql, int qr) {
    if (ql <= xl and xr <= qr)
        return sums[xi];
    int xm = (xl + xr) >> 1, ans = 0;
    if (ql <= xm and qr >= xl)
        ans += query_sum_helper(xi << 1, xl, xm, ql, qr);
    if (ql <= xr and qr > xm)
        ans += query_sum_helper((xi << 1) | 1, xm + 1, xr, ql, qr);
    return ans;
}

int query_sum(int ll, int rr) {
    return query_sum_helper(1, 0, n - 1, ll, rr);
}

void init_ds(int maxv) {
    ds[1] = 1;
    for (int i = 2; i <= maxv; ++i)
        ds[i] = 2;
    for (int i = 2, b = maxv / 2 + 2; i <= b; ++i)
        for (int j = i + i; j <= maxv; j += i)
            ds[j] += 1;
}

int main() {
    ios::sync_with_stdio(0);
    int q, v, maxv = 0;
    cin >> n >> q;
    for (int i = 0; i < n; ++i) {
        cin >> v;
        maxv = max(maxv, v);
        arr[i] = v;
    }
    printf("(1) n=%d, q=%d, maxv=%d\n", n, q, maxv);
    init_ds(maxv);
    build_helper(1, 0, n - 1);

    for (int i = 0; i <= maxv; ++i) printf("%d,", ds[i]);
    printf("\n");

    for (int i = 0; i < q; ++i) {
        int op, ll, rr;
        cin >> op >> ll >> rr;
        // printf("(2) op=%d, ll=%d, rr=%d\n", op, ll, rr);
        --ll;
        --rr;
        if (op == 1) dec(ll, rr);
        else printf("%d\n", query_sum(ll, rr));
    }
    return 0;
}
