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;
int const MAXN = 1e6 + 9;
int d[MAXN], p[MAXN];
int n;
int nxt[MAXN];
long long int tree[4 * MAXN], a[MAXN];
int cal(int x) {
  int ans = 1;
  int s = p[x], cnt = 1;
  while (x > 1) {
    x /= s;
    if (p[x] != s) {
      ans *= (cnt + 1);
      cnt = 1;
      s = p[x];
    } else
      cnt++;
  }
  return ans;
}
int find(int x) {
  if (x == nxt[x]) return x;
  return nxt[x] = find(nxt[x]);
}
void build(int node, int start, int end) {
  if (start == end) {
    tree[node] = a[start];
    return;
  }
  int mid = (start + end) / 2;
  build(2 * node, start, mid);
  build(2 * node + 1, mid + 1, end);
  tree[node] = tree[2 * node] + tree[2 * node + 1];
}
void update(int node, int start, int end, int idx) {
  if (start == end) {
    a[idx] = d[a[idx]];
    tree[node] = a[idx];
    return;
  }
  int mid = (start + end) / 2;
  if (start <= idx and idx <= mid)
    update(2 * node, start, mid, idx);
  else
    update(2 * node + 1, mid + 1, end, idx);
  tree[node] = tree[2 * node] + tree[2 * node + 1];
}
long long int query(int node, int start, int end, int l, int r) {
  if (r < start or end < l) return 0;
  if (l <= start and end <= r) return tree[node];
  int mid = (start + end) / 2;
  long long int p1 = query(2 * node, start, mid, l, r);
  long long int p2 = query(2 * node + 1, mid + 1, end, l, r);
  return (p1 + p2);
}
void myupdate(int l, int r) {
  l--;
  for (int i = find(l); i < r; i = find(i + 1)) {
    update(1, 0, n - 1, i);
    if (a[i] == 2 or a[i] == 1) nxt[i] = i + 1;
  }
}
int main() {
  p[0] = 0;
  p[1] = 1;
  for (int i = 0; i < MAXN; i++) p[i] = i, nxt[i] = i;
  for (int i = 2; i < MAXN; i++)
    if (p[i] == i)
      for (int j = 2 * i; j < MAXN; j += i)
        if (p[j] == j) p[j] = i;
  d[1] = 1;
  for (int i = 2; i < MAXN; i++) d[i] = cal(i);
  ios_base::sync_with_stdio(0), cin.tie(0);
  int q;
  cin >> n >> q;
  for (int i = 0; i < n; i++) cin >> a[i];
  build(1, 0, n - 1);
  while (q--) {
    int t, l, r;
    cin >> t >> l >> r;
    if (l > r) swap(l, r);
    if (t == 1) {
      myupdate(l, r);
    } else {
      cout << query(1, 0, n - 1, --l, --r) << "\n";
    }
  }
}