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 math
from math import ceil, log2


def getMiddle(start, end):
    return start + (end - start) // 2


def RMQU(segmentTree, startSegment, endSegment, i, j, index):
    if i <= startSegment and j >= endSegment:
        return segmentTree[index]

    if endSegment < i or startSegment > j:
        return 0

    mid = getMiddle(startSegment, endSegment)
    return RMQU(segmentTree, startSegment, mid, i, j, 2 * index + 1) + RMQU(segmentTree, mid + 1, endSegment, i, j, 2 * index + 2)


def RMQ(segmentTree, n, i, j):
    if i < 0 or j > n - 1 or i > j:
        return -1

    return RMQU(segmentTree, 0, n - 1, i, j, 0)


def updateValue(arr, segmentTree, startSegment, endSegment, index, value, n):
    if index < startSegment or index > endSegment:
        return

    if startSegment == endSegment:

        arr[index] = value
        segmentTree[n] = value
    else:
        mid = getMiddle(startSegment, endSegment)

        if index >= startSegment and index <= mid:
            updateValue(arr, segmentTree, startSegment, mid, index,
                        value, 2 * n + 1)
        else:
            updateValue(arr, segmentTree, mid + 1, endSegment,
                        index, value, 2 * n + 2)

        segmentTree[n] = segmentTree[2 * n + 1] + segmentTree[2 * n + 2]
    return


def buildSegmentTree(arr, startSegment, endSegment, segmentTree, startIndex):
    if startSegment == endSegment:
        segmentTree[startIndex] = arr[startSegment]
        return arr[startSegment]

    mid = getMiddle(startSegment, endSegment)
    segmentTree[startIndex] = buildSegmentTree(arr, startSegment, mid, segmentTree, startIndex * 2 + 1) + buildSegmentTree(arr, mid + 1, endSegment, segmentTree, startIndex * 2 + 2)

    return segmentTree[startIndex]


def initSegmentTree(arr, n):
    x = int(ceil(log2(n)))
    maxSize = 2 * (int)(2 ** x) - 1
    segmentTree = [0] * maxSize
    buildSegmentTree(arr, 0, n - 1, segmentTree, 0)
    return segmentTree


def getDivisors(n):
    counter = 0
    for i in range(1, int(math.sqrt(n)) + 1):
        if n % i == 0:

            if n / i == i:
                counter = counter + 1
            else:
                counter = counter + 2

    return counter


def main():
    n, m = list(map(int, input().split(' ')))
    arr = list(map(int, input().split(' ')))
    segmentTree = initSegmentTree(arr, n)

    for i in range(m):
        operation, x, y = list(map(int, input().split(' ')))
        #replace
        if operation == 1:
            for i in range(x,y+1):
                numDivisors = getDivisors(arr[i-1])
                updateValue(arr, segmentTree, 0, n - 1, i-1, numDivisors, 0)
        #query
        else:
            print(RMQ(segmentTree, n, x-1, y-1))

main()

	  		 			      	     					   	