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 long long MAXN = 3e5 + 1;
long long N, M;
long long a[MAXN];
long long d[1000001];
namespace SGT {
long long data_sum[MAXN << 2], data_max[MAXN << 2];
inline void push_up(long long now) {
  data_sum[now] = data_sum[now << 1] + data_sum[now << 1 | 1];
  data_max[now] = max(data_max[now << 1], data_max[now << 1 | 1]);
}
inline void build(long long l, long long r, long long now) {
  if (l == r) {
    data_sum[now] = data_max[now] = a[l];
    return;
  }
  long long mid = l + r >> 1;
  build(l, mid, now << 1);
  build(mid + 1, r, now << 1 | 1);
  push_up(now);
}
inline void upd(long long ul, long long ur, long long l, long long r,
                long long now) {
  if (l == r) {
    data_sum[now] = data_max[now] = d[data_max[now]];
    return;
  }
  long long mid = l + r >> 1;
  if (ul <= mid && data_max[now << 1] > 2) upd(ul, ur, l, mid, now << 1);
  if (ur > mid && data_max[now << 1 | 1] > 2)
    upd(ul, ur, mid + 1, r, now << 1 | 1);
  push_up(now);
}
inline long long query(long long ql, long long qr, long long l, long long r,
                       long long now) {
  if (ql <= l && r <= qr) return data_sum[now];
  long long mid = l + r >> 1, ans = 0;
  if (ql <= mid) ans += query(ql, qr, l, mid, now << 1);
  if (qr > mid) ans += query(ql, qr, mid + 1, r, now << 1 | 1);
  return ans;
}
}  // namespace SGT
using namespace SGT;
signed main() {
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
  cin >> N >> M;
  for (register long long i = 1; i <= 1000000; i++)
    for (register long long j = i; j <= 1000000; j += i) d[j]++;
  for (register long long i = 1; i <= N; i++) cin >> a[i];
  build(1, N, 1);
  long long opt, x, y;
  while (M--) {
    cin >> opt >> x >> y;
    if (opt == 1)
      upd(x, y, 1, N, 1);
    else
      cout << query(x, y, 1, N, 1) << endl;
  }
  return 0;
}