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;
namespace NODD {
vector<int> primes;
void sieve(int n) {
  vector<bool> mark(n + 2, false);
  primes.push_back(2);
  for (int p = 3; p * p <= n; p = p + 2)
    if (mark[p] == 0)
      for (int i = p * p; i <= n; i += p * 2) mark[i] = 1;
  for (int i = 3; i <= n; i = i + 2)
    if (!mark[i]) primes.push_back(i);
}
int NOD(long long n) {
  int div = 1;
  for (int i = 0; (long long)primes[i] * (long long)primes[i] <= n; i++) {
    int cnt = 0;
    while (n % primes[i] == 0) {
      n = n / primes[i];
      cnt++;
    }
    div *= (cnt + 1);
  }
  if (n > 1) div *= 2;
  return div;
}
}  // namespace NODD
template <typename T>
class fenwick {
  int n;
  vector<T> tree;

 public:
  fenwick() : n(2e5), tree(n + 5, 0) {}
  fenwick(int _n) : n(_n), tree(n + 5, 0) {}
  void init(int _n) { n = -n, tree.assign(n + 5, 0); }
  void Update(int pos, T val, int limit) {
    while (pos <= limit) {
      tree[pos] += val;
      pos += pos & (-pos);
    }
  }
  T Query(int pos) {
    T sum = 0;
    while (pos > 0) {
      sum += tree[pos];
      pos -= pos & (-pos);
    }
    return sum;
  }
};
using namespace NODD;
vector<int> cnt(1e6 + 2, -1);
void solve() {
  sieve(10000);
  for (int i = 1; i <= 1000000; i++) cnt[i] = NOD((long long)i);
  int n, q;
  cin >> n >> q;
  fenwick<long long> fen(n);
  set<int> st;
  vector<int> v = {0};
  for (int in, i = 1; i <= n; i++) {
    cin >> in;
    fen.Update(i, in, n);
    if (cnt[in] != in) st.insert(i);
    v.push_back(in);
  }
  while (q--) {
    int choose, l, r;
    cin >> choose >> l >> r;
    if (choose == 1) {
      l--;
      while (true) {
        if (st.upper_bound(l) == st.end()) break;
        l = *st.upper_bound(l);
        if (l > r) break;
        fen.Update(l, -v[l], n);
        v[l] = cnt[v[l]];
        fen.Update(l, v[l], n);
        if (v[l] == cnt[v[l]]) st.erase(l);
      }
    } else {
      cout << fen.Query(r) - fen.Query(l - 1) << "\n";
    }
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  int tc = 1;
  while (tc--) {
    solve();
  }
  return 0;
}