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;
struct Sum {
  long long operator()(long long x, long long y) { return x + y; }
};
template <class T, class BinOp, T id>
class SegTree {
  vector<T>& A;
  vector<T> tree;
  BinOp op;
  long long from, to;
  long long left(long long i) { return i << 1; }
  long long right(long long i) { return (i << 1) + 1; }
  void build(long long node, long long l, long long r) {
    if (tree.size() <= node) tree.resize(node + 1);
    if (l == r) {
      tree[node] = A[l];
    } else {
      long long mid = (l + r) / 2;
      build(left(node), l, mid);
      build(right(node), mid + 1, r);
      tree[node] = op(tree[left(node)], tree[right(node)]);
    }
  }
  T rq(long long node, long long l, long long r, long long ql, long long qr) {
    if (l > qr || ql > r) return id;
    if (ql <= l && r <= qr) return tree[node];
    long long mid = (l + r) / 2;
    return op(rq(left(node), l, mid, ql, qr),
              rq(right(node), mid + 1, r, ql, qr));
  }
  void upd(long long node, long long l, long long r, long long qi, T qval) {
    if (l == r && l == qi) {
      tree[node] = qval;
      return;
    }
    long long mid = (l + r) / 2;
    if (qi <= mid)
      upd(left(node), l, mid, qi, qval);
    else
      upd(right(node), mid + 1, r, qi, qval);
    tree[node] = op(tree[left(node)], tree[right(node)]);
  }

 public:
  SegTree(vector<T>& A, long long from, long long to)
      : A(A), from(from), to(to), op(BinOp()) {
    build(1, from, to);
  }
  T rq(long long ql, long long qr) { return rq(1, from, to, ql, qr); }
  void upd(long long qi, T qval) {
    A[qi] = qval;
    upd(1, from, to, qi, qval);
  }
};
long long constexpr A = 1e6 + 1;
long long n, m, d[A];
signed main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  for (long long i = 1; i < A; ++i) {
    for (long long j = i; j < A; j += i) d[j] += 1;
  }
  cin >> n >> m;
  vector<long long> a(n + 1);
  set<pair<long long, long long>> st;
  for (long long i = 1; i <= n; ++i) {
    cin >> a[i];
    if (a[i] > 2) st.insert({i, a[i]});
  }
  SegTree<long long, Sum, 0> segtree(a, 1, n);
  long long t, l, r;
  while (m--) {
    cin >> t >> l >> r;
    if (t != 1)
      cout << segtree.rq(l, r) << '\n';
    else {
      vector<pair<long long, long long>> to_insert;
      for (auto it = st.upper_bound({l - 1, A}); it != st.end();) {
        pair<long long, long long> v = *it;
        if (v.first > r) break;
        v.second = d[v.second];
        segtree.upd(v.first, v.second);
        if (v.second > 2) to_insert.push_back(v);
        it = st.erase(it);
      }
      for (auto& v : to_insert) st.insert(v);
    }
  }
}