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 <img align="middle" class="tex-formula" src="https://espresso.codeforces.com/6afb5e3d414ffbb040c175e23c6627da949add06.png" style="max-width: 100.0%;max-height: 100.0%;"/> replace *a*<sub class="lower-index">*i*</sub> with *D*(*a*<sub class="lower-index">*i*</sub>); 1.  SUM *l* *r* — calculate <img align="middle" class="tex-formula" src="https://espresso.codeforces.com/1e50b9417bb7e50d92d43134922596e938249431.png" style="max-width: 100.0%;max-height: 100.0%;"/>. 
Print the answer for each SUM query.
The first line contains two integers *n* and *m* (1 ≤ *n*, *m* ≤ 3·10<sup class="upper-index">5</sup>) — the number of elements in the array and the number of queries to process, respectively.

The second line contains *n* integers *a*<sub class="lower-index">1</sub>, *a*<sub class="lower-index">2</sub>, ..., *a*<sub class="lower-index">*n*</sub> (1 ≤ *a*<sub class="lower-index">*i*</sub> ≤ 10<sup class="upper-index">6</sup>) — the elements of the array.

Then *m* lines follow, each containing 3 integers *t*<sub class="lower-index">*i*</sub>, *l*<sub class="lower-index">*i*</sub>, *r*<sub class="lower-index">*i*</sub> denoting *i*-th query. If *t*<sub class="lower-index">*i*</sub> = 1, then *i*-th query is REPLACE *l*<sub class="lower-index">*i*</sub> *r*<sub class="lower-index">*i*</sub>, otherwise it's SUM *l*<sub class="lower-index">*i*</sub> *r*<sub class="lower-index">*i*</sub> (1 ≤ *t*<sub class="lower-index">*i*</sub> ≤ 2, 1 ≤ *l*<sub class="lower-index">*i*</sub> ≤ *r*<sub class="lower-index">*i*</sub> ≤ *n*).

There is at least one SUM query.
none
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
30
13
4
22
4 2
1 1 1 3
1 1 4
2 1 4
5
10 2
1 1 1 1 1 1 1 1 1 9
1 1 10
2 1 10
12
4 2
1 1 3 1
1 1 4
2 1 4
5
5 3
1 1 1 1 3
2 1 5
1 1 5
2 1 5
7
6
7 10
1 1 1 1 1 1 1
1 1 7
1 1 7
1 1 7
1 1 7
1 1 7
1 1 7
1 1 7
1 1 7
1 1 7
2 1 7
7
import sys
from collections import defaultdict, deque, Counter
from decimal import *
from heapq import heapify, heappop, heappush
import math
import random
import string
from copy import deepcopy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

def input():
    return sys.stdin.readline().rstrip()
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getListGraph():
    return list(map(lambda x:int(x) - 1, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]

mod = 10 ** 9 + 7
MOD = 998244353
# sys.setrecursionlimit(10000000)
# import pypyjit
# pypyjit.set_param('max_unroll_recursion=-1')
inf = float('inf')
eps = 10 ** (-12)
dy = [0, 1, 0, -1]
dx = [1, 0, -1, 0]

#############
# Main Code #
#############

# 0-index サイズ気持ち大きめで建てて
# 要素が重複していても使える
class BIT:
    def __init__(self, N):
        self.N = N
        self.bit = [0] * (N + 1)
        self.b = 1 << N.bit_length() - 1

    def add(self, a, w):
        x = a + 1
        while(x <= self.N):
            self.bit[x] += w
            x += x & -x

    def get(self, a):
        ret, x = 0, a
        while(x > 0):
            ret += self.bit[x]
            x -= x & -x
        return ret

    def cum(self, l, r):
        return self.get(r) - self.get(l)

    # xより左にあるフラグのうちもっとも右にあるフラグを探す
    # bit.get(x)そもそも左にフラグがあるか　なければlowerboundは0を示すが0にフラグはない
    # bit.lowerbound(bit.get(x)) 探す
    # bit.lowerbound(bit.get(x) + 1) 自身あるいは自身より右位にあるフラグのうち一番左にあるものを探す
    def lowerbound(self, w):
        if w <= 0:
            return -1
        x = 0
        k = self.b
        while k > 0:
            if x + k <= self.N and self.bit[x + k] < w:
                w -= self.bit[x + k]
                x += k
            k //= 2
        return x

# 約数列挙
def make_divisors(n):
    divisors = []
    for i in range(1, int(math.sqrt(n)) + 1):
        if n % i == 0:
            divisors.append(i)
            # √nで無い数についてもう一個プラス
            if i != n // i:
                divisors.append(n // i)
    return sorted(divisors)

"""
D(a): aの約数の個数
6 4 1 10 3 2 4
1 3 5の場合1→1 10→4 3→2
6 4 1 4 2 2 4
6 4 1 4 2 2 3

最終的に2になる　動かす回数はそんなに多くない
範囲内の3以上のとこだけ動かす
[1, 1, 0, 1, 1, 0, 1]
"""
N, M = getNM()
A = getList()

bit_sum = BIT(N)
bit_flag = BIT(N)
for i in range(N):
    bit_sum.add(i, A[i])
    if A[i] >= 3:
        bit_flag.add(i, 1)

# print([bit_flag.cum(i, i + 1) for i in range(N)])
dic = {}
for _ in range(M):
    d, l, r = getNM()
    l -= 1
    r -= 1
    l = bit_flag.lowerbound(bit_flag.get(l) + 1)
    if d == 1:
        while l <= r:
            val = bit_sum.cum(l, l + 1)
            nxt_val = len(make_divisors(val))
            bit_sum.add(l, nxt_val - val)
            # フラグは消す
            if nxt_val <= 2:
                bit_flag.add(l, -1)
            # 次
            l = bit_flag.lowerbound(bit_flag.get(l + 1) + 1)
    if d == 2:
        print(bit_sum.cum(l, r + 1))