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;
vector<string> split(string s, string border);
vector<long long> t;
long long n;
void init(long long nn) {
  n = nn;
  t.assign(n, 0);
}
long long sum(long long r) {
  long long result = 0;
  for (; r >= 0; r = (r & (r + 1)) - 1) result += t[r];
  return result;
}
void inc(long long i, long long delta) {
  for (; i < n; i = (i | (i + 1))) t[i] += delta;
}
long long sum(long long l, long long r) { return sum(r) - sum(l - 1); }
void init(vector<long long> a) {
  init((long long)a.size());
  for (unsigned i = 0; i < a.size(); i++) inc(i, a[i]);
}
vector<long long> D;
void solve() {
  long long n;
  cin >> n;
  long long m;
  cin >> m;
  D = vector<long long>(1e6);
  for (long long i = 0; i < (1e6); i++) D[i] = 0;
  for (long long i = (1); i < (1e6); i++) {
    long long pos = i;
    while (pos < 1e6) {
      D[pos]++;
      pos += i;
    }
  }
  vector<long long> a(n);
  for (long long i = 0; i < (n); i++) cin >> a[i];
  ;
  init(a);
  set<long long> calc;
  for (long long i = 0; i < (n); i++) {
    if (a[i] > 2) calc.insert(i);
  }
  for (long long test = 0; test < (m); test++) {
    long long t;
    cin >> t;
    long long l;
    cin >> l;
    l--;
    long long r;
    cin >> r;
    r--;
    if (t == 1) {
      auto it = calc.lower_bound(l);
      while (it != calc.end() && (*it) <= r) {
        long long now_val = sum((*it), (*it));
        inc(*it, D[now_val] - now_val);
        if (D[now_val] == 2)
          it = calc.erase(it);
        else
          ++it;
      }
    } else {
      cout << sum(l, r) << endl;
    }
  }
}
signed main(signed argc, char* argv[]) {
  ios_base::sync_with_stdio(0);
  cin.tie();
  if (argc > 1 && (string)argv[1] == "file") {
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    long long number_sample = 1;
    do {
      cout << "Sample #" << number_sample << ":" << endl;
      cerr << "Sample #" << number_sample << ":" << endl;
      solve();
      number_sample++;
      cout << endl;
      cerr << endl;
    } while (!cin.eof());
  } else {
    cerr.clear(ios_base::badbit);
    solve();
  }
}
vector<string> split(string s, string border) {
  vector<string> ans;
  long long pos_end;
  while ((pos_end = s.find(border)) != string::npos) {
    if (pos_end) ans.push_back(s.substr(0, pos_end));
    s = s.substr(pos_end + border.size());
  }
  return ans;
}