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;
using namespace std;
long long getSum(long long BITree[], long long index) {
  long long sum = 0;
  index = index + 1;
  while (index > 0) {
    sum += BITree[index];
    index -= index & (-index);
  }
  return sum;
}
void updateBIT(long long BITree[], long long n, long long index,
               long long val) {
  index = index + 1;
  while (index <= n) {
    BITree[index] += val;
    index += index & (-index);
  }
}
long long *constructBITree(long long *arr, long long n) {
  long long *BITree = new long long[n + 1];
  for (long long i = 1; i <= n; i++) BITree[i] = 0;
  for (long long i = 0; i < n; i++) updateBIT(BITree, n, i, arr[i]);
  return BITree;
}
vector<long long> primes;
long long a[300001];
vector<vector<long long> > table;
long long D[1000001];
void sieve(long long n) {
  bool prime[n + 1];
  memset(prime, true, sizeof(prime));
  for (int p = 2; p * p <= n; p++) {
    if (prime[p] == true) {
      for (int i = p * 2; i <= n; i += p) prime[i] = false;
    }
  }
  for (int i = 2; i <= n; i++) {
    if (prime[i]) primes.push_back(i);
  }
}
long long getD(long long num) {
  if (D[num] != -1) return D[num];
  if (num == 1) {
    D[num] = 1;
    return D[num];
  }
  for (int i = 0; i < primes.size(); i++) {
    if (primes[i] > sqrt(num)) {
      D[num] = 2;
      return D[num];
    }
    if (num % primes[i] == 0) {
      int curr = 0;
      long long temp = num;
      while (num % primes[i] == 0) {
        curr++;
        num = num / primes[i];
      }
      D[temp] = (curr + 1) * getD(num);
      return D[temp];
    }
  }
  return -1;
}
void buildTable(int i) {
  long long num = a[i];
  table[i].push_back(num);
  while (getD(num) != num) {
    table[i].push_back(getD(num));
    num = getD(num);
  }
}
int n, m;
map<int, int> ptr;
long long *btree;
int main(void) {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  ;
  sieve(1000000);
  memset(D, -1, sizeof(D));
  cin >> n >> m;
  table.resize(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i];
    buildTable(i);
    ptr[i] = 0;
  }
  btree = constructBITree(a, n);
  for (int i = 0; i < m; i++) {
    int t, l, r;
    cin >> t >> l >> r;
    l--, r--;
    if (t == 1) {
      map<int, int>::iterator it = ptr.lower_bound(l);
      while (it != ptr.end() && it->first <= r) {
        it->second++;
        if (it->second < table[it->first].size()) {
          updateBIT(
              btree, n, it->first,
              table[it->first][it->second] - table[it->first][it->second - 1]);
          it++;
        } else {
          it = ptr.erase(it);
        }
      }
    } else {
      if (l == 0) {
        cout << getSum(btree, r) << endl;
      } else {
        cout << getSum(btree, r) - getSum(btree, l - 1) << endl;
      }
    }
  }
}