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 N = 1e5;
long long int sg[12 * N + 20];
int sgmx[12 * N + 20];
int arr[3 * N + 5];
int dp[10 * N + 11];
void init(int l, int r, int k) {
  if (l == r) {
    sg[k] = arr[l];
    return;
  }
  int mid = (l + r) / 2;
  init(l, mid, 2 * k);
  init(mid + 1, r, 2 * k + 1);
  sg[k] = sg[2 * k] + sg[2 * k + 1];
}
void init2(int l, int r, int k) {
  if (l == r) {
    sgmx[k] = arr[l];
    return;
  }
  int mid = (l + r) / 2;
  init2(l, mid, 2 * k);
  init2(mid + 1, r, 2 * k + 1);
  sgmx[k] = max(sgmx[2 * k], sgmx[2 * k + 1]);
}
void count_divisors() {
  int temp, n, cr;
  dp[1] = 1;
  dp[2] = 2;
  bool s;
  for (int i = 3; i <= 10 * N; i++) {
    temp = i;
    bool broken = false;
    for (int j = 2; j * j * j <= i; j++) {
      if (temp % j == 0) {
        cr = 0;
        while (temp % j == 0) {
          cr++;
          temp /= j;
        }
        dp[i] = (cr + 1) * (dp[temp]);
        broken = true;
        break;
      }
    }
    if (!broken) {
      if ((int)sqrt(temp) * (int)sqrt(temp) == temp) {
        dp[i] = 3;
      } else if (temp > 1) {
        bool isp = true;
        for (int k = 2; k <= sqrt(temp); k++) {
          if (temp % k == 0) {
            isp = false;
            break;
          }
        }
        if (isp)
          dp[i] = 2;
        else
          dp[i] = 4;
      } else
        dp[i] = 1;
    }
  }
}
long long int find_sum(int l, int r, int sorgu_sol, int sorgu_sag, int k) {
  if (l > sorgu_sag || r < sorgu_sol) return 0;
  if (l >= sorgu_sol && r <= sorgu_sag) {
    return sg[k];
  }
  int mid = (l + r) / 2;
  return find_sum(l, mid, sorgu_sol, sorgu_sag, 2 * k) +
         find_sum(mid + 1, r, sorgu_sol, sorgu_sag, 2 * k + 1);
}
void q_replace(int l, int r, int sorgu_sol, int sorgu_sag, int k) {
  if (r < l || l > sorgu_sag || r < sorgu_sol || sgmx[k] <= 2) return;
  if (l == r) {
    sg[k] = dp[sg[k]];
    sgmx[k] = sg[k];
    return;
  }
  int mid = (l + r) / 2;
  q_replace(l, mid, sorgu_sol, sorgu_sag, 2 * k);
  q_replace(mid + 1, r, sorgu_sol, sorgu_sag, 2 * k + 1);
  sg[k] = sg[2 * k] + sg[2 * k + 1];
  sgmx[k] = max(sgmx[2 * k], sgmx[2 * k + 1]);
}
int main() {
  cin.tie(0);
  ios::sync_with_stdio(0);
  int n, m, qt, l, r;
  cin >> n >> m;
  for (int i = 1; i <= n; i++) cin >> arr[i];
  init(1, n, 1);
  init2(1, n, 1);
  count_divisors();
  while (m--) {
    cin >> qt >> l >> r;
    if (qt == 1)
      q_replace(1, n, l, r, 1);
    else
      cout << find_sum(1, n, l, r, 1) << "\n";
  }
  return 0;
}