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;
template <typename T1, typename T2>
bool umin(T1& x, const T2& y) {
  return (x > y ? (x = y, true) : false);
}
template <typename T1, typename T2>
bool umax(T1& x, const T2& y) {
  return (x < y ? (x = y, true) : false);
}
template <typename T>
void read(T& x) {
  char ch;
  T p = 1;
  x = 0;
  do {
    ch = getchar();
  } while (ch <= ' ');
  if (ch == '-') p = -1, ch = getchar();
  while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
  x *= p;
}
void read(string& x) {
  char ch;
  do {
    ch = getchar();
  } while (ch <= ' ');
  while (ch > ' ') x += ch, ch = getchar();
}
void read(char& x) {
  do {
    x = getchar();
  } while (x <= ' ');
}
template <typename T, typename... R>
void read(T& x, R&... y) {
  read(x);
  read(y...);
}
const int N = (int)1e6 + 3;
const int INF = (int)1e9 + 17;
const long long mod = (long long)1e9;
const long long LLINF = (long long)1e18 + 17;
const long double pi = (long double)acos(-1.0);
int n, m;
int to[N];
int a[N];
long long t[4 * N];
int psh[N];
multiset<int> tree[4 * N];
int get(int x) {
  int ret = 0;
  for (int d = 1; d * d <= x; ++d) {
    if (x % d != 0) continue;
    ret += 1 + (x / d != d);
  }
  return ret;
}
void build(int v, int tl, int tr) {
  if (tl == tr) {
    tree[v].insert(a[tl]);
    t[v] += a[tl];
    return;
  }
  int tm = (tl + tr) / 2;
  build(v + v, tl, tm);
  build(v + v + 1, tm + 1, tr);
  t[v] = t[v + v] + t[v + v + 1];
}
void apply(int v, int val, int idx, int tl, int tr) {
  if (tl == tr) {
    t[v] = val;
    return;
  }
  int tm = (tl + tr) / 2;
  if (idx <= tm)
    apply(v + v, val, idx, tl, tm);
  else
    apply(v + v + 1, val, idx, tm + 1, tr);
  t[v] = t[v + v] + t[v + v + 1];
}
long long get(int v, int tl, int tr, int l, int r) {
  if (r < tl || tr < l) return 0;
  if (l <= tl && tr <= r) return t[v];
  int tm = (tl + tr) / 2;
  return get(v + v, tl, tm, l, r) + get(v + v + 1, tm + 1, tr, l, r);
}
int main() {
  read(n, m);
  for (int i = (0); i < (n); i++) read(a[i]);
  set<pair<int, int> > c;
  for (int i = (0); i < (n); i++) {
    c.insert(make_pair(i, a[i]));
    long long x = a[i];
    while (to[x] == 0) {
      to[x] = get(x);
      x = to[x];
    }
  }
  build(1, 0, n - 1);
  while (m-- > 0) {
    int tp, l, r;
    read(tp, l, r);
    if (tp == 1) {
      auto lf = c.lower_bound(make_pair(l - 1, -INF));
      auto rg = c.upper_bound(make_pair(r - 1, INF));
      vector<pair<int, int> > cp(lf, rg);
      for (pair<int, int> x : cp) {
        c.erase(x);
        if (x.second != to[x.second]) {
          apply(1, to[x.second], x.first, 0, n - 1);
          c.insert(make_pair(x.first, to[x.second]));
        }
      }
    }
    if (tp == 2) printf("%I64d\n", get(1, 0, n - 1, l - 1, r - 1));
  }
  return 0;
}