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;
const int M = 1e6 + 1;
const int N = 3e5 + 1;
const int P = 1e5 + 1;
int arr[N];
int one[N];
int lp[M];
int p[P];
int cur;
int n, q;
long long bit[N];
pair<int, int> d[M];
struct Dsu {
  int par[N];
  int cnt[N];
  int nxt[N];
} dsu;
void update(int i, int key) {
  for (; i < N; i += (i & -i)) bit[i] += key;
}
long long query(int i) {
  long long res = 0;
  for (; i; i -= (i & -i)) res += bit[i];
  return res;
}
void sieve() {
  for (int i = 2; i < M; ++i) {
    if (!lp[i]) {
      lp[i] = p[cur++] = i;
      d[i] = {1, 2};
    }
    for (int j = 0; j < cur && p[j] <= lp[i] && i * p[j] < M; ++j) {
      lp[i * p[j]] = p[j];
      if (lp[i] == p[j]) {
        d[i * p[j]] = {d[i].first, d[i].second + 1};
      } else {
        d[i * p[j]] = {d[i].first * d[i].second, 2};
      }
    }
  }
}
int findset(int u) {
  return (dsu.par[u] == u ? u : dsu.par[u] = findset(dsu.par[u]));
}
void unite(int u, int v) {
  u = findset(u);
  v = findset(v);
  if (u == v) return;
  if (dsu.cnt[u] < dsu.cnt[v]) {
    swap(u, v);
  }
  dsu.nxt[u] = max(dsu.nxt[u], dsu.nxt[v]);
  dsu.cnt[u] += dsu.cnt[v];
  dsu.par[v] = u;
}
long long query(int l, int r) {
  return query(r) - query(l - 1) - (one[r] - one[l - 1]);
}
void replace(int l, int r) {
  for (int i = dsu.nxt[findset(l)]; i <= r; i = dsu.nxt[findset(i)] + 1) {
    update(i, d[arr[i]].first * d[arr[i]].second - arr[i]);
    arr[i] = d[arr[i]].first * d[arr[i]].second;
    if (arr[i] == 2) {
      if (arr[i - 1] == 2) {
        unite(i, i - 1);
      }
      if (arr[i + 1] == 2) {
        unite(i, i + 1);
      }
    }
  }
}
void input() {
  cin >> n >> q;
  for (int i = 1; i <= n; ++i) {
    cin >> arr[i];
    dsu.par[i] = i;
    dsu.nxt[i] = i;
    dsu.cnt[i] = 1;
    one[i] = one[i - 1];
    if (arr[i] == 1) {
      arr[i] = 2;
      one[i]++;
    }
    update(i, arr[i]);
  }
}
void solve() {
  for (int i = 0; i < q; ++i) {
    int t;
    cin >> t;
    int l;
    cin >> l;
    int r;
    cin >> r;
    if (t == 1) {
      replace(l, r);
    } else {
      cout << query(l, r) << "\n";
    }
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0), cout.tie(0);
  sieve();
  input();
  solve();
}