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 long long MAXN = 300005;
long long n, m, a, b, c, num[MAXN];
int yz[1000005];
int chge[1000005];
string t;
struct tree {
  long long l, r, sum, tim;
} tree[MAXN << 2];
void update(long long p) {
  tree[p].sum = tree[(p << 1)].sum + tree[(p << 1 | 1)].sum;
}
void build(long long l, long long r, long long p) {
  tree[p].tim = 0;
  tree[p].l = l, tree[p].r = r;
  if (l == r) {
    tree[p].sum = num[l];
    return;
  }
  long long mid = (tree[p].l + tree[p].r) >> 1;
  build(l, mid, (p << 1));
  build(mid + 1, r, (p << 1 | 1));
  update(p);
}
void change(long long l, long long r, long long p) {
  if (tree[p].l >= l && tree[p].r <= r) {
    if (tree[p].tim >= 20) return;
    tree[p].tim++;
  }
  if (tree[p].l == tree[p].r) {
    tree[p].sum = yz[num[tree[p].l]];
    num[tree[p].l] = yz[num[tree[p].l]];
    return;
  }
  long long mid = (tree[p].l + tree[p].r) >> 1;
  if (l <= mid) change(l, r, (p << 1));
  if (mid < r) change(l, r, (p << 1 | 1));
  update(p);
}
long long ask_sum(long long l, long long r, long long p) {
  if (l <= tree[p].l && tree[p].r <= r) return tree[p].sum;
  long long ans = 0, mid = (tree[p].l + tree[p].r) >> 1;
  if (l <= mid) ans += ask_sum(l, r, (p << 1));
  if (mid < r) ans += ask_sum(l, r, (p << 1 | 1));
  update(p);
  return ans;
}
int YinZi(int n) {
  int ans = 1;
  for (int i = 2; i * i <= n; i++) {
    if (n % i == 0) {
      int num = 0;
      while (n % i == 0) {
        num++;
        n = n / i;
      }
      ans *= (num + 1);
    }
  }
  if (n > 1) ans *= 2;
  return ans;
}
void init() {
  memset(yz, 0, sizeof(yz));
  for (int i = 1; i < 1000005; i++) {
    yz[i] = YinZi(i);
    chge[i] = yz[i] - i;
  }
}
int maxx = 0;
int dp[1000005];
int main() {
  init();
  while (~scanf("%d%d", &n, &m)) {
    memset(num, 0, sizeof(num));
    for (int i = 1; i <= n; i++) {
      scanf("%I64d", &num[i]);
    }
    build(1, n, 1);
    int op, l, r;
    while (m--) {
      scanf("%d%d%d", &op, &l, &r);
      if (op == 1) {
        change(l, r, 1);
      } else {
        printf("%I64d\n", ask_sum(l, r, 1));
      }
    }
  }
}