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 Matrix {
  vector<vector<int>> data;
  int r, c;
  Matrix(int row, int col, bool identity = false) : r(row), c(col) {
    data.assign(row, vector<int>(col, 0));
    if (identity) {
      for (int i = 0; i < r; ++i) {
        data[i][i] = 1;
      }
    }
  }
  Matrix operator*(Matrix& other) {
    int m = r, n = c, p = other.c;
    Matrix res(m, p);
    for (int i = 0; i < m; ++i) {
      for (int j = 0; j < p; ++j) {
        for (int k = 0; k < n; ++k) {
          res.data[i][j] += data[i][k] * other.data[k][j];
        }
      }
    }
    return res;
  }
};
vector<int> extendGcd(int a, int b) {
  if (b == 0) {
    return {a, 1, 0};
  } else {
    vector<int> tmp = extendGcd(b, a % b);
    return {tmp[0], tmp[2], tmp[1] - (a / b) * tmp[2]};
  }
}
Matrix matrix_power(Matrix base, long long exp) {
  int n = base.r;
  Matrix res(n, n, true);
  while (exp) {
    if (exp & 1) {
      res = res * base;
    }
    base = base * base;
    exp >>= 1;
  }
  return res;
}
template <typename T>
T power_mod(T base, int exp, int mod = 1000000007) {
  T res = 1;
  while (exp) {
    if (exp & 1) res = res * base % mod;
    base = base * base % mod;
    exp >>= 1;
  }
  return res;
}
template <typename T>
T power(T base, int exp) {
  T res = 1;
  while (exp) {
    if (exp & 1) res *= base;
    base *= base;
    exp >>= 1;
  }
  return res;
}
long long inv(long long a) { return power_mod(a, 1000000007 - 2); }
int n, m;
int cnt[1000010];
int a[300010];
long long sum[300010 << 2];
int ma[300010 << 2];
void build(int index, int begin, int end) {
  if (begin == end) {
    sum[index] = a[begin];
    ma[index] = a[begin];
  } else {
    build((index << 1), begin, (((begin) + (end)) / 2));
    build(((index << 1) | 1), (((begin) + (end)) / 2) + 1, end);
    sum[index] = sum[(index << 1)] + sum[((index << 1) | 1)];
    ma[index] = max(ma[(index << 1)], ma[((index << 1) | 1)]);
  }
}
long long query(int index, int begin, int end, int l, int r) {
  if (begin > r || end < l) return 0;
  if (l <= begin && end <= r) return sum[index];
  long long q1 = query((index << 1), begin, (((begin) + (end)) / 2), l, r);
  long long q2 =
      query(((index << 1) | 1), (((begin) + (end)) / 2) + 1, end, l, r);
  return q1 + q2;
}
void update(int index, int begin, int end, int l, int r) {
  if (l <= begin && end <= r) {
    if (ma[index] <= 2) return;
    for (int i = begin; i <= end; ++i) {
      a[i] = cnt[a[i]];
    }
    build(index, begin, end);
  } else {
    if (l <= (((begin) + (end)) / 2)) {
      update((index << 1), begin, (((begin) + (end)) / 2), l, r);
    }
    if (r > (((begin) + (end)) / 2)) {
      update(((index << 1) | 1), (((begin) + (end)) / 2) + 1, end, l, r);
    }
    sum[index] = sum[(index << 1)] + sum[((index << 1) | 1)];
    ma[index] = max(ma[(index << 1)], ma[((index << 1) | 1)]);
  }
}
int main() {
  for (int i = 1; i < 1000010; ++i) {
    for (int j = i; j < 1000010; j += i) {
      cnt[j]++;
    }
  }
  cin >> n >> m;
  for (int i = 1; i <= n; ++i) {
    scanf("%d", a + i);
  }
  build(1, 1, n);
  int t, l, r;
  for (int i = 0; i < m; ++i) {
    scanf("%d%d%d", &t, &l, &r);
    if (t == 1) {
      update(1, 1, n, l, r);
    } else {
      cout << query(1, 1, n, l, r) << endl;
    }
  }
  return 0;
}