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;
class Timer {
 private:
  string scope_name;
  chrono::high_resolution_clock::time_point start_time;

 public:
  Timer(string name) : scope_name(name) {
    start_time = chrono::high_resolution_clock::now();
  }
  ~Timer() {
    auto stop_time = chrono::high_resolution_clock::now();
    auto length =
        chrono::duration_cast<chrono::microseconds>(stop_time - start_time)
            .count();
    double mlength = double(length) * 0.001;
    ;
  }
};
const long long MOD = 1000000007;
const long long INF = 0x3f3f3f3f3f3f3f3f;
const int iNF = 0x3f3f3f3f;
const long long MAXN = 300005;
const long long MAXC = 1000006;
int n, m, a[MAXN], d[MAXC];
set<int> rem;
long long bit[MAXN];
void add(int x, int val) {
  for (; x < MAXN; x += -x & x) {
    bit[x] += val;
  }
}
long long qry(int x) {
  long long ret = 0;
  for (; x > 0; x -= -x & x) {
    ret += bit[x];
  }
  return ret;
}
int main() {
  ;
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  {
    ;
    for (int i = 1; i < MAXC - 1 + 1; i += 1) {
      for (int j = i; j < MAXC; j += i) {
        d[j]++;
      }
    };
  }
  cin >> n >> m;
  for (int i = 1; i < n + 1; i += 1) {
    cin >> a[i];
    if (d[a[i]] != a[i]) {
      rem.insert(i);
    }
    add(i, a[i]);
  }
  while (m--) {
    int t, l, r;
    cin >> t >> l >> r;
    if (t == 1) {
      while (true) {
        auto ptr = rem.lower_bound(l);
        if (ptr == rem.end() || *ptr > r) {
          break;
        } else {
          int cur = *ptr;
          add(cur, d[a[cur]] - a[cur]);
          a[cur] = d[a[cur]];
          if (d[a[cur]] == a[cur]) {
            rem.erase(cur);
          }
          l = cur + 1;
        }
      }
    } else {
      cout << qry(r) - qry(l - 1) << '\n';
    }
  }
  return 0;
}