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 maxn = 1000005;
const int lim = 1200005;
int divnum[maxn];
int maxx[lim];
long long int soma[lim];
vector<int> g;
void init() {
  for (int i = 2; i < maxn; i++) {
    divnum[i] = 1;
  }
  for (int i = 2; i < maxn; i++) {
    for (int j = i; j < maxn; j += i) {
      divnum[j]++;
    }
  }
}
void makeTree(int pos, int i, int j) {
  if (i == j) {
    soma[pos] = g[i];
    maxx[pos] = g[i];
  } else {
    int esquerda = 2 * pos;
    int direita = 2 * pos + 1;
    int meio = (i + j) / 2;
    makeTree(esquerda, i, meio);
    makeTree(direita, meio + 1, j);
    soma[pos] = soma[esquerda] + soma[direita];
    maxx[pos] = max(maxx[esquerda], maxx[direita]);
  }
}
void atualiza(int pos, int i, int j, int a, int b) {
  if (maxx[pos] <= 2) {
    return;
  }
  if (i == j) {
    soma[pos] = divnum[soma[pos]];
    maxx[pos] = soma[pos];
    return;
  }
  int esquerda = 2 * pos;
  int direita = 2 * pos + 1;
  int meio = (i + j) / 2;
  if (a <= meio) {
    atualiza(esquerda, i, meio, a, b);
  }
  if (b > meio) {
    atualiza(direita, meio + 1, j, a, b);
  }
  soma[pos] = soma[esquerda] + soma[direita];
  maxx[pos] = max(maxx[esquerda], maxx[direita]);
}
long long int consulta(int pos, int i, int j, int a, int b) {
  if (a <= i && j <= b) {
    return soma[pos];
  }
  if (a > j || b < i) {
    return 0;
  }
  int esquerda = 2 * pos;
  int direita = 2 * pos + 1;
  int meio = (i + j) / 2;
  return consulta(esquerda, i, meio, a, b) +
         consulta(direita, meio + 1, j, a, b);
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int n, q;
  init();
  cin >> n >> q;
  g.resize(n + 1);
  for (int i = 1; i <= n; i++) {
    cin >> g[i];
  }
  makeTree(1, 1, n);
  while (q--) {
    int op, a, b;
    cin >> op >> a >> b;
    if (op == 1) {
      atualiza(1, 1, n, a, b);
    } else {
      cout << consulta(1, 1, n, a, b) << endl;
    }
  }
}