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;
int64_t n, t, arb2[3 * 4 * (100003)], v[300005], ciur2[1000006], l, r, pos, val;
int arb1[3 * 4 * (100003)];
void build1(int64_t nod, int64_t lo, int64_t hi) {
  if (lo == hi)
    arb1[nod] = v[lo];
  else {
    int64_t m = (lo + hi) >> 1;
    build1(nod << 1, lo, m);
    build1(nod << 1 | 1, m + 1, hi);
    arb1[nod] = max(arb1[nod << 1], arb1[nod << 1 | 1]);
  }
}
void build2(int64_t nod, int64_t lo, int64_t hi) {
  if (lo == hi)
    arb2[nod] = v[lo];
  else {
    int64_t m = (lo + hi) >> 1;
    build2(nod << 1, lo, m);
    build2(nod << 1 | 1, m + 1, hi);
    arb2[nod] = arb2[nod << 1] + arb2[nod << 1 | 1];
  }
}
void update(int64_t nod, int64_t st, int64_t dr) {
  if (arb1[nod] <= 2) return;
  if (st == dr) {
    int64_t newval = ciur2[arb1[nod]];
    arb1[nod] = newval;
    arb2[nod] = newval;
    return;
  }
  if (st >= l && dr <= r) {
    int64_t m = (st + dr) >> 1;
    update(nod << 1, st, m);
    update(nod << 1 | 1, m + 1, dr);
    arb1[nod] = max(arb1[nod << 1], arb1[nod << 1 | 1]);
    arb2[nod] = arb2[nod << 1] + arb2[nod << 1 | 1];
  } else {
    int64_t m = (st + dr) >> 1;
    if (m >= l) update(nod << 1, st, m);
    if (m < r) update(nod << 1 | 1, m + 1, dr);
    arb1[nod] = max(arb1[nod << 1], arb1[nod << 1 | 1]);
    arb2[nod] = arb2[nod << 1] + arb2[nod << 1 | 1];
  }
}
int64_t query2(int64_t nod, int64_t st, int64_t dr) {
  if (st >= l && dr <= r) return arb2[nod];
  int64_t m = (st + dr) >> 1, ans = 0;
  if (m >= l) ans = query2(nod << 1, st, m);
  if (m < r) ans += query2(nod << 1 | 1, m + 1, dr);
  return ans;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cin.tie(NULL);
  cin >> n >> t;
  for (int64_t i = 1; i <= n; ++i) cin >> v[i];
  build1(1, 1, n);
  build2(1, 1, n);
  for (int64_t i = 1; i <= 1000000; ++i)
    for (int64_t j = i; j <= 1000000; j += i) ++ciur2[j];
  while (t--) {
    int64_t test;
    cin >> test >> l >> r;
    if (test == 1)
      update(1, 1, n);
    else
      cout << query2(1, 1, n) << "\n";
  }
  return 0;
}