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 JAVA):

Solution:
import java.util.*;
import java.io.*;
import java.math.BigInteger; 
public class lp{ 
static PrintWriter out = new PrintWriter(System.out);

static void fun(int div[])
{
       for(int i=1;i<div.length;i++)
          for(int j=i;j<div.length;j=j+i)
              div[j]++;
}
static void update(long BIT[],int i,int sum)
{
     while(i<BIT.length)
       {
           BIT[i] = BIT[i]+sum;
               i = i + (i&(-i));        
        }
}
static long sum(long BIT[],int i)
{
     long s=0;
    while(i>0)
      {
             s=s+BIT[i];
             i = i - (i&(-i));
      }
   return s;
}
static int find(int x,int p[])
{
     if(x==p[x])
        return x;
      return p[x] = find(p[x],p);
}

static void update(int l,int r,long bit[],int p[],int a[],int ct[],int div[],int n)
{
      for(int i=l;i<=r;)
        {
            int root = find(i,p);
            if(root>r)
               return;
            update(bit,root+1,div[a[root]]-a[root]);
            a[root] = div[a[root]];
            ct[root]++;
            if(ct[root]==10)
              {
                 int rr = find(root+1,p);                
                 p[root]=rr;
               }
            i=root+1;
        }        
}
static void solve() {

int div[] = new int[1000002];
fun(div);
int n = ni();
int m = ni();
int a[] = ai(n);
int ct[] = new int[n];
int p[] = new int[n+1];
long bit[] = new long[n+1];
for(int i=0;i<n;i++){
     update(bit,i+1,a[i]);
     p[i]=i;
}
 
     p[n]=n;
for(int o=1;o<=m;o++)
{

int t = ni();
int l=ni();
int r = ni();
if(t==1)
 update(l-1,r-1,bit,p,a,ct,div,n);
else{
long s = sum(bit,r)-sum(bit,l-1);
  pn(s);
}
}
 
   out.flush();
}
public static void main(String[] args) throws Exception{


// use this block when you need more recursion depth
new Thread(null, null, "Name", 999999999) {
            public void run() {
                try {
                    solve();
                } catch(Exception e) {
                    e.printStackTrace();
                    System.exit(1);
                }
            }
        }.start();  
} 
static int[] ai(int n)  // it will give in array of size n
{
    int a[] = new int[n];
    for(int i=0;i<n;i++)
        a[i] = ni();
    return a;
}
static long[] al(int n)  // it will give in array of size n
{
    long a[] = new long[n];
    for(int i=0;i<n;i++)
        a[i] = nl();
    return a;
}
 
static void p(Object o)
{
   out.print(o);
}
static void pn(Object o)
{
    out.println(o);
}
static int abs(int x)
{
    return x>0 ? x : -x;
}
static long gcd(long a,long b)
{
       if(a==0)
          return b;
       if(b==0)
          return a;
       if(b%a==0)
          return a;
          return gcd(b%a,a);
}
static int count_set(int n)
{
   int c=0;
while(n>0)
{
   if(n%2==1)
     c++;
     n=n/2;
}
   return c;
}
static void subtract_1(char s[]) // it will subtract 1 from the given number.  number should be positive
{
      if(s[0]=='0') // number is zero
          return;
     int n = s.length,i=n-1;
     while(s[i]=='0')
       i--;
     s[i] = (char)((int)(s[i]-'0') + 47);
   
     for(int j=i+1;j<n;j++)
         s[j]='9';
}
static long pow(long a,long b,long md)
{ 
    long ans=1;
    while(b>0)
    {
         if(b%2==1)
           ans = (ans*a)%md;
           a = (a*a)%md;
           b = b/2;
    }
   return ans;
}
static long min(long a,long b){
 
     return a<b ? a : b;
}
static long max(long a,long b){
     return a>b ? a : b;
}
static boolean pal(String s)
{
   int n = s.length(),i1=0,i2=n-1;
 
     while(i1<i2)
     {
        if(s.charAt(i1)!=s.charAt(i2))
             return false;
             i1++; i2--;
     }
       return true;
}
static String rev(String r)
{
    String s = "";
    int i= r.length()-1;
 
    while(i>=0)
    {
        s=s+r.charAt(i);
        i--;   
    }
       return s;
}
static FastReader sc=new FastReader(); 
 
      static int ni(){
                 int x = sc.nextInt();
                 return(x);
        }
      static long nl(){
              long x = sc.nextLong();
              return(x);
         }
      static String n(){
                 String str = sc.next();
                     return(str);
       }
     static String ns(){
                 String str = sc.nextLine();
                   return(str);
      }
     static double nd(){
               double d = sc.nextDouble();
                 return(d);
       }
  static class FastReader 
    { 
        BufferedReader br; 
        StringTokenizer st; 
  
        public FastReader() 
        { 
            br = new BufferedReader(new
                     InputStreamReader(System.in)); 
        } 
  
        String next() 
        { 
            while (st == null || !st.hasMoreElements()) 
            { 
                try
                { 
                    st = new StringTokenizer(br.readLine()); 
                } 
                catch (IOException  e) 
                { 
                    e.printStackTrace(); 
                } 
            } 
            return st.nextToken(); 
        } 
  
        int nextInt() 
        { 
            return Integer.parseInt(next()); 
        } 
  
        long nextLong() 
        { 
            return Long.parseLong(next()); 
        } 
  
        double nextDouble() 
        { 
            return Double.parseDouble(next()); 
        } 
  
        String nextLine() 
        { 
            String str = ""; 
            try
            { 
                str = br.readLine(); 
            } 
            catch (IOException e) 
            { 
                e.printStackTrace(); 
            } 
            return str; 
        } 
    } 
}