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;
const int block_size = 320;
const long long mod = 1e9 + 7;
const long long inf = 1e9 + 7;
const long double eps = 1e-9;
const double PI = atan(1) * 4;
template <typename T>
inline int sign(const T& a) {
  if (a < 0) return -1;
  if (a > 0) return 1;
  return 0;
}
template <typename T, typename S>
inline bool upmin(T& a, const S& b) {
  return a > b ? a = b, 1 : 0;
}
template <typename T, typename S>
inline bool upmax(T& a, const S& b) {
  return a < b ? a = b, 1 : 0;
}
template <typename T>
inline void in(T& x) {
  x = 0;
  T f = 1;
  char ch = getchar();
  while (!isdigit(ch)) {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (isdigit(ch)) {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  x *= f;
}
long long twop(int x) { return 1LL << x; }
template <typename A, typename B>
inline void in(A& x, B& y) {
  in(x);
  in(y);
}
template <typename A, typename B, typename C>
inline void in(A& x, B& y, C& z) {
  in(x);
  in(y);
  in(z);
}
template <typename A, typename B, typename C, typename D>
inline void in(A& x, B& y, C& z, D& d) {
  in(x);
  in(y);
  in(z);
  in(d);
}
int v[300010];
int fac[1000010];
struct SegTree {
  static const int maxn = 300010;
  struct node {
    int l, r;
    long long max, sum;
  };
  node no[maxn * 4];
  void push_up(int ind) {
    no[ind].max = max(no[(ind << 1)].max, no[(ind << 1 | 1)].max);
    no[ind].sum = no[(ind << 1)].sum + no[(ind << 1 | 1)].sum;
  }
  void push_down(int ind) { return; }
  void build(int l, int r, int ind) {
    no[ind].l = l;
    no[ind].r = r;
    if (l == r) {
      no[ind].sum = no[ind].max = v[l];
    } else {
      int mid = (l + r) / 2;
      build(l, mid, (ind << 1));
      build(mid + 1, r, (ind << 1 | 1));
      push_up(ind);
    }
  }
  void update(int l, int r, int ind) {
    if (l > no[ind].r || r < no[ind].l) return;
    if (no[ind].max <= 2) return;
    if (no[ind].l == no[ind].r) {
      no[ind].sum = no[ind].max = fac[no[ind].sum];
    } else {
      update(l, r, (ind << 1));
      update(l, r, (ind << 1 | 1));
      push_up(ind);
    }
  }
  void query(int l, int r, int ind, long long& ans) {
    if (l > no[ind].r || r < no[ind].l) return;
    if (l <= no[ind].l && no[ind].r <= r) {
      ans += no[ind].sum;
    } else {
      query(l, r, (ind << 1), ans);
      query(l, r, (ind << 1 | 1), ans);
    }
  }
};
int dp[1000010];
SegTree tree;
int main() {
  for (long long i = 1; i < 1000010; i++) {
    for (int j = i; j < 1000010; j += i) {
      fac[j] += 1;
    }
  }
  cerr << "fac[2]"
       << " = " << (fac[2]) << endl;
  ;
  cerr << "fac[6]"
       << " = " << (fac[6]) << endl;
  ;
  cerr << "fac[2 * 3 * 5]"
       << " = " << (fac[2 * 3 * 5]) << endl;
  ;
  cerr << "fac[1000000]"
       << " = " << (fac[1000000]) << endl;
  ;
  int ans = 1;
  int n, m;
  in(n, m);
  for (long long i = 1; i < n + 1; i++) in(v[i]);
  tree.build(1, n, 1);
  while (m--) {
    int a, l, r;
    in(a, l, r);
    if (a == 1) {
      tree.update(l, r, 1);
    } else {
      long long ans = 0;
      tree.query(l, r, 1, ans);
      printf("%lld\n", ans);
    }
  }
  return 0;
}