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;
int n, m, G[5555555], P[5555555], tree[5555555];
long long sum[5555555];
int read() {
  char c = getchar();
  int ans = 0;
  while (c < '0' || c > '9') c = getchar();
  while (c >= '0' && c <= '9')
    ans = (ans << 1) + (ans << 3) + (c ^ 48), c = getchar();
  return ans;
}
void buildtree(int L, int R, int rt) {
  if (L == R) {
    tree[rt] = sum[rt] = G[L];
    return;
  }
  int mid = (L + R) >> 1;
  buildtree(L, mid, rt << 1);
  buildtree(mid + 1, R, rt << 1 | 1);
  tree[rt] = max(tree[rt << 1], tree[rt << 1 | 1]);
  sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];
  return;
}
void change(int L, int R, int l, int r, int rt) {
  if (L == R) {
    G[L] = P[G[L]];
    tree[rt] = sum[rt] = G[L];
    return;
  }
  if (tree[rt] <= 2) return;
  int mid = (L + R) >> 1;
  if (mid >= l) change(L, mid, l, r, rt << 1);
  if (mid < r) change(mid + 1, R, l, r, rt << 1 | 1);
  tree[rt] = max(tree[rt << 1], tree[rt << 1 | 1]);
  sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];
  return;
}
long long query(int L, int R, int l, int r, int rt) {
  if (l <= L && R <= r) return sum[rt];
  if (l > R || L > r) return 0;
  int mid = (L + R) >> 1;
  return query(L, mid, l, r, rt << 1) + query(mid + 1, R, l, r, rt << 1 | 1);
}
int main() {
  n = read(), m = read();
  for (int i = 1; i <= 1000000; i++) {
    P[i] = 1;
    int k = i;
    for (int j = 2; j * j <= k; j++) {
      int now = 0;
      while (k % j == 0) k /= j, ++now;
      P[i] *= (now + 1);
    }
    if (k != 1) P[i] <<= 1;
  }
  for (int i = 1; i <= n; i++) G[i] = read();
  buildtree(1, n, 1);
  for (int i = 1, x, y, z; i <= m; i++) {
    x = read(), y = read(), z = read();
    if (x == 1)
      change(1, n, y, z, 1);
    else
      printf("%lld\n", query(1, n, y, z, 1));
  }
  return 0;
}