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 INF = 0x3f3f3f3f;
const long long mod = 1000000007;
const double e = 2.718281828459;
long long gcd(long long a, long long b) {
  if (!b) return a;
  return gcd(b, a % b);
}
long long gcd1(int a, int b) {
  if (!b) return a;
  return gcd(b, a % b);
}
long long pow_mod(long long a, long long b, long long c) {
  long long ans = 1;
  a = a % c;
  while (b > 0) {
    if (b % 2 == 1) ans = (ans * a) % c;
    b = b / 2;
    a = (a * a) % c;
  }
  return ans;
}
int pow_int(int a, int b) {
  int ans = 1;
  while (b > 0) {
    if (b % 2 == 1) ans = ans * a;
    b = b / 2;
    a = a * a;
  }
  return ans;
}
long long pow_llong(long long a, long long b) {
  long long ans = 1;
  while (b > 0) {
    if (b % 2 == 1) ans = ans * a;
    b = b / 2;
    a = a * a;
  }
  return ans;
}
const int dx[9] = {0, 1, 1, 1, 0, -1, -1, -1, 0};
const int dy[9] = {0, 1, 0, -1, -1, -1, 0, 1, 1};
int Scan() {
  int res = 0, flag = 0;
  char ch;
  if ((ch = getchar()) == '-') {
    flag = 1;
  } else if (ch >= '0' && ch <= '9') {
    res = ch - '0';
  }
  while ((ch = getchar()) >= '0' && ch <= '9') {
    res = res * 10 + (ch - '0');
  }
  return flag ? -res : res;
}
void Out(int a) {
  if (a < 0) {
    putchar('-');
    a = -a;
  }
  if (a >= 10) {
    Out(a / 10);
  }
  putchar(a % 10 + '0');
}
long long jc_mod(long long a, long long b, long long mod) {
  long long ans = 1;
  b = max(b, a - b);
  for (long long i = a; i > b; i--) {
    ans *= i;
    ans %= mod;
  }
  return ans;
}
double lg(double a) { return (log(a) / log(10.0)); }
int lowbit(int x) { return x & -x; }
inline int read() {
  int f = 1, x = 0;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  return x * f;
}
void lisan(int *x, int n) {
  int data[100010];
  for (int i = 1; i <= n; i++) data[i] = x[i];
  sort(data + 1, data + 1 + n);
  int o = unique(data + 1, data + 1 + n) - data - 1;
  for (int i = 1; i <= n; i++)
    x[i] = lower_bound(data + 1, data + 1 + o, x[i]) - data;
}
void emain() {
  freopen("in.txt", "w", stdout);
  cout << 100 << endl;
  for (int i = 1; i <= 100; i++) {
    srand(time(NULL) / i);
    int m = rand() % i + 5;
    cout << 1000 << " " << m << endl;
    for (int i = 1; i <= 1000; i++) cout << rand() % (i * i) + 100340038 << " ";
    cout << endl;
  }
}
int euler[1000007];
void Init() {
  for (int i = 1; i <= 1000007 - 1; i++) {
    for (int j = i; j < 1000007; j += i) euler[j]++;
  }
}
const int maxn = 1000007;
struct tree {
  int l, r;
  long long sum;
  int maxv;
} tr[maxn << 2];
int a[maxn << 2];
void build(int id, int x, int y) {
  tr[id].l = x;
  tr[id].r = y;
  if (x == y) {
    tr[id].sum = tr[id].maxv = a[x];
  } else {
    int mid = (x + y) >> 1;
    build((id << 1), x, mid);
    build((id << 1 | 1), mid + 1, y);
    tr[id].sum = tr[(id << 1)].sum + tr[(id << 1 | 1)].sum;
    tr[id].maxv = max(tr[(id << 1)].maxv, tr[(id << 1 | 1)].maxv);
  }
}
void update(int ql, int qr, int id) {
  if (qr < tr[id].l || ql > tr[id].r || tr[id].r < tr[id].l) return;
  if (ql <= tr[id].l && qr >= tr[id].r && tr[id].maxv <= 2) return;
  if (tr[id].l == tr[id].r) {
    tr[id].maxv = tr[id].sum = euler[tr[id].sum];
  } else {
    int mid = (tr[id].l + tr[id].r) >> 1;
    if (ql <= mid) update(ql, qr, (id << 1));
    if (qr > mid) update(ql, qr, (id << 1 | 1));
    tr[id].sum = tr[(id << 1)].sum + tr[(id << 1 | 1)].sum;
    tr[id].maxv = max(tr[(id << 1)].maxv, tr[(id << 1 | 1)].maxv);
  }
}
long long query(int x, int y, int id) {
  if (x <= tr[id].l && y >= tr[id].r)
    return tr[id].sum;
  else {
    int mid = (tr[id].l + tr[id].r) >> 1;
    if (x > mid)
      return query(x, y, (id << 1 | 1));
    else if (y <= mid)
      return query(x, y, (id << 1));
    else {
      return query(x, y, (id << 1 | 1)) + query(x, y, (id << 1));
    }
  }
}
int main() {
  int n, m;
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
  build(1, 1, n);
  Init();
  for (int i = 1; i <= m; i++) {
    int a, b, c;
    scanf("%d%d%d", &a, &b, &c);
    if (a == 1)
      update(b, c, 1);
    else
      printf("%I64d\n", query(b, c, 1));
  }
  return 0;
}