Problem: 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 <image> replace ai with D(ai); 
  2. SUM l r — calculate <image>. 



Print the answer for each SUM query.

Input

The first line contains two integers n and m (1 ≤ n, m ≤ 3·105) — the number of elements in the array and the number of queries to process, respectively.

The second line contains n integers a1, a2, ..., an (1 ≤ ai ≤ 106) — the elements of the array.

Then m lines follow, each containing 3 integers ti, li, ri denoting i-th query. If ti = 1, then i-th query is REPLACE li ri, otherwise it's SUM li ri (1 ≤ ti ≤ 2, 1 ≤ li ≤ ri ≤ n).

There is at least one SUM query.

Output

For each SUM query print the answer to it.

Example

Input

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


Output

30
13
4
22

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
long long int minprime[1000005];
long long int divisor[1000005];
long long int BIT[1000005];
long long int parent[1000005];
set<long long int> st;
set<long long int>::iterator it, ind, it1;
void sieve() {
  for (long long int i = 2; i * i <= 1000005; i++) {
    if (minprime[i] == 0) {
      for (long long int j = i * i; j <= 1000005; j += i) {
        if (minprime[j] == 0) minprime[j] = i;
      }
    }
  }
  for (long long int i = 2; i <= 1000005; i++) {
    if (minprime[i] == 0) {
      minprime[i] = i;
    }
  }
}
vector<long long int> factors(long long int n) {
  vector<long long int> res;
  while (n != 1) {
    res.push_back(minprime[n]);
    n /= minprime[n];
  }
  return res;
}
void calc() {
  long long int i, j;
  divisor[1] = 1;
  for (i = 2; i <= 1000004; i++) {
    long long int res = 1;
    vector<long long int> vect;
    map<long long int, long long int> mp;
    map<long long int, long long int>::iterator it;
    vect = factors(i);
    for (j = 0; j < vect.size(); j++) mp[vect[j]]++;
    for (it = mp.begin(); it != mp.end(); it++) res = res * (it->second + 1);
    divisor[i] = res;
  }
}
void formation(long long int index, long long int val, long long int n) {
  long long int i;
  for (i = index; i <= n; i += i & (-i)) {
    BIT[i] += val;
  }
}
void update(long long int index, long long int val, long long int n) {
  long long int i;
  for (i = index; i <= n; i += i & (-i)) {
    BIT[i] += val;
  }
}
long long int query(long long int index, long long int n) {
  long long int i, ans = 0;
  while (index > 0) {
    ans += BIT[index];
    index -= index & (-index);
  }
  return ans;
}
int main() {
  int start_s = clock();
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  long long int i, j, k, m, t, n, l, r, ans1, ans2, ini, curr, add, val,
      newvalue, oldvalue;
  sieve();
  calc();
  cin >> n >> m;
  long long int arr[n + 1];
  for (i = 1; i <= n; i++) {
    cin >> arr[i];
    if (arr[i] > 2) st.insert(i);
    formation(i, arr[i], n);
  }
  for (i = 0; i < m; i++) {
    cin >> t >> l >> r;
    if (t == 1) {
      ind = st.lower_bound(l);
      for (it = ind; (it != st.end()) && ((*it) <= r);) {
        val = *it;
        newvalue = divisor[arr[val]];
        oldvalue = arr[val];
        add = newvalue - oldvalue;
        arr[val] = newvalue;
        update(val, add, n);
        if (newvalue <= 2) {
          it1 = it;
          it1++;
          st.erase(it);
          it = it1;
        } else {
          it++;
        }
      }
    } else {
      ans2 = query(r, n);
      ans1 = query(l - 1, n);
      cout << (ans2 - ans1) << "\n";
    }
  }
}