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
from sys import stdin
input=lambda :stdin.readline()[:-1]

import bisect


class BIT_SortedSet:
    def __init__(self, A, compress=True, sort_flag=False):
        self.compress = compress
        self.N = len(A)
        self.log = 0
        while self.N >= 1 << (self.log + 1):
            self.log += 1
        if compress:
            if sort_flag:
                self.A = A
            else:
                self.A = sorted(A)
            self.index_dic = {}
            for i in range(len(A)):
                self.index_dic[self.A[i]] = i
        else:
            self.A = A
        self.BIT = [0] * (self.N + 5)
        self.size = 0
        self.cnt = [0] * self.N

    def BIT_add(self, i, x):
        idx = i + 1
        while idx < self.N + 1:
            self.BIT[idx] += x
            idx += idx & (-idx)

    def BIT_query(self, i):
        res = 0
        idx = i + 1
        while idx:
            res += self.BIT[idx]
            idx -= idx & (-idx)
        return res

    def BIT_lower_left(self, w):
        if w <= 0 or w > self.size:
            return None
        x = 0
        k = 1 << self.log
        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 __contains__(self, x):
        if self.compress:
            x = self.index_dic[x]
        return self.cnt[x] >= 1

    def __len__(self):
        return self.size

    def add(self, x):
        if self.compress:
            x = self.index_dic[x]
        if self.cnt[x] == 1:
            return False
        self.BIT_add(x, 1)
        self.size += 1
        self.cnt[x] += 1
        return True

    def discard(self, x):
        if self.compress:
            x = self.index_dic[x]
        if self.cnt[x] > 0:
            self.BIT_add(x, -1)
            self.size -= 1
            self.cnt[x] -= 1
            return True
        return False

    def find_kth_val(self, k):
        res = self.BIT_lower_left(k + 1)
        if res == None:
            return None
        if self.compress:
            res = self.A[res]
        return res

    def __getitem__(self, x):
        if x < 0:
            x += self.size
        if x < 0 or x >= self.size:
            raise IndexError
        return self.find_kth_val(x)

    def index_right(self, x):
        if self.N == 0:
            return 0
        if x < self.A[0]:
            return 0
        if self.compress:
            y = bisect.bisect_right(self.A, x) - 1
        else:
            y = min(x, self.N - 1)
        return self.BIT_query(y)

    def index(self, x):
        if self.N == 0:
            return 0
        if x <= self.A[0]:
            return 0
        if self.compress:
            y = bisect.bisect_right(self.A, x) - 1
        else:
            y = x
        if y >= self.N:
            y = self.N - 1
        elif self.A[y] == x:
            y -= 1
        return self.BIT_query(y)

    def gt(self, x):
        return self.find_kth_val(self.index_right(x))

    def ge(self, x):
        return self.find_kth_val(self.index(x))

    def lt(self, x):
        return self.find_kth_val(self.index(x) - 1)

    def le(self, x):
        return self.find_kth_val(self.index_right(x) - 1)

    def __str__(self):
        return (
            "{"
            + ", ".join(map(str, [self.find_kth_val(i) for i in range(self.size)]))
            + "}"
        )

class segtree():
  def __init__(self,init,func,ide):
    self.n=len(init)
    self.func=func
    self.ide=ide
    self.size=1<<(self.n-1).bit_length()
    self.tree=[self.ide for i in range(2*self.size)]
    for i in range(self.n):
      self.tree[self.size+i]=init[i]
    for i in range(self.size-1,0,-1):
      self.tree[i]=self.func(self.tree[2*i], self.tree[2*i|1])
  
  def update(self,k,x):
    k+=self.size
    self.tree[k]=x
    k>>=1
    while k:
      self.tree[k]=self.func(self.tree[2*k],self.tree[k*2|1])
      k>>=1
  
  def get(self,i):
    return self.tree[i+self.size]
  
  def query(self,l,r):
    l+=self.size
    r+=self.size
    l_res=self.ide
    r_res=self.ide
    while l<r:
      if l&1:
        l_res=self.func(l_res,self.tree[l])
        l+=1
      if r&1:
        r-=1
        r_res=self.func(self.tree[r],r_res)
      l>>=1
      r>>=1
    return self.func(l_res,r_res)
  
  def debug(self,s=10):
    print([self.get(i) for i in range(min(self.n,s))])

m=10**6+10
d=[0]*m
for i in range(1,m):
  for j in range(i,m,i):
    d[j]+=1

n,q=map(int,input().split())
a=list(map(int,input().split()))
S=BIT_SortedSet(list(range(n+1)))
S.add(n)
for i in range(n):
  if a[i]>=2:
    S.add(i)

seg=segtree(a,lambda x,y:x+y,0)
for _ in range(q):
  t,l,r=map(lambda x:int(x)-1,input().split())
  if t==0:
    while True:
      x=S.ge(l)
      if x>r:
        break
      a[x]=d[a[x]]
      seg.update(x,a[x])
      if a[x]>=2:
        S.discard(x)
      l=x+1
  else:
    print(seg.query(l,r+1))