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.io.IOException;
import java.util.*;


public class SUMandREPLACE {
    static int[] num   = new int[1000001] ;
    static int[] count = new int[1000001] ;
    static int[] numC  = new int[1000001] ;   
    static boolean[] sieve = new boolean[1000001];
    
    static class point{
          long sum ;
          boolean local;
          boolean all  ;
          
          point(long sum,boolean all,boolean local){
              this.sum    = sum ;
              this.local  = local  ;
              this.all = all ;
           }
          
        static public point get(point p1,point p2){
            int sum =0 ;
            boolean flagAll   = false; 
            boolean flagLocal = false;
            
            if(p1.all==true&&p2.all==true){
                flagAll = true ;
            }
            
            if(p1.local==true||p2.local==true){
                flagLocal= true ;
            }
            
            return new point(p1.sum+p2.sum,flagAll,flagLocal) ;
        } 
    }

   static point[] sTree ; // sTree[1] dem so phan tu a[i] nho hon max   
   static int N ;
   
   static void init(int n,int[] a){
        N = 1;
        while(N<n) N *= 2 ;
        sTree = new point[2*N] ;
        
        for(int i = 0;i<N;i++){
            if(i<n){
                boolean flag = (a[i]!=1&&a[i]!=2)? true:false ; 
        	sTree[i+N] = new point(a[i],flag,flag) ;
            }else 
                sTree[i+N] = new point(0,false,false) ;
        }
            
        for(int i=N-1;i>=1;i--){
            sTree[i] = point.get(sTree[2*i],sTree[2*i+1]);   
        } 
   }
    
   static void update(int k){ // update phan tu a[k] = v   
       
       k+= N;    // update tren segment tree
       
       int cur = (int) sTree[k].sum ;
       cur = count[cur];
       boolean flag = (cur!=1&&cur!=2)? true:false ;
       
        sTree[k] = new point(cur,flag,flag) ;    
        //System.out.println("U "+k+" "+cur);
        while(k/2 > 0){
           k=k/2;
           sTree[k] = point.get(sTree[2*k],sTree[2*k+1]) ;
        }
    }
    
   static void updateRange(int a,int b,int k,int l,int r){ //[)
       if(r<=a||b<=l) return ;
       if(a<=l&&r<=b){
        //System.out.println("To "+k);   
           if(sTree[k].all==true){
               int cof = 1;
               while(k*cof<N) cof*=2;
                for(int i=k*cof;i<(k+1)*cof;i++)
                    update(i-N);  
            }else if(sTree[k].local==false){
                return;
            }else{
                updateRange(a,b,2*k,l,(l+r)/2);
                updateRange(a,b,2*k+1,(l+r)/2,r);
            }
        }else{
           updateRange(a,b,2*k,l,(l+r)/2);
           updateRange(a,b,2*k+1,(l+r)/2,r);
        } 
    }
   
    static long count(int a,int b,int k,int l,int r){ 
        if(r<=a||b<=l) return 0 ;
        if(a<=l&&r<=b) return sTree[k].sum ;
        else{
            long vl = count(a,b,2*k,l,(l+r)/2);
            long vr = count(a,b,2*k+1,(l+r)/2,r);
            return vl+vr ;
        }
    }
    

    public static void main(String[] args) {
        
    
    for(int i=0;i<=1000000;i++){
        num[i]  = i ;
        count[i]= 1 ;
    }
    
    Arrays.fill(sieve, true);
    sieve[0] = sieve[1] = false ;
        
    for(int i=2;i<=1000000;i++){
            if(sieve[i]==false) continue ;
            else{
                int suft = i;
                count[suft] = 2;
                
                while(suft+i<=1000000){
                    suft += i;
                    sieve[suft] = false ;
                    int get = num[suft];
                    int cur = 0;
                    
                    while(get%i==0){
                        cur++; 
                        get/=i;
                    }
                    
                    num[suft] = get ;
                    count[suft] *= (cur+1);
                }
            }
        }
    
        //System.out.println(count[999]);
        for(int i=1;i<=1000000;i++){
            int cur=0;
            int c = i;
            while(c!=1&&c!=2){
                c=count[c];
                cur++;
            }
            numC[i] = cur ;
        }
        
        //int[] a = {6,6,6,6};
        
        /*
        init(a.length,a);
        for(int i=4;i<8;i++)
        System.out.print(i!=7?sTree[i].sum+" ":sTree[i].sum+"\n") ;
        updateRange(0,4,1,0,N);
        for(int i=4;i<8;i++)
        System.out.print(i!=7?sTree[i].sum+" ":sTree[i].sum+"\n") ;
        updateRange(1,4,1,0,N);
        for(int i=4;i<8;i++)
        System.out.print(i!=7?sTree[i].sum+" ":sTree[i].sum+"\n");
        updateRange(1,3,1,0,N);
        for(int i=4;i<8;i++)
        System.out.print(i!=7?sTree[i].sum+" ":sTree[i].sum+"\n");
        updateRange(0,4,1,0,N);
        for(int i=4;i<8;i++)
        System.out.print(i!=7?sTree[i].sum+" ":sTree[i].sum+"\n");
        */
        int n = ni() ;
        int m = ni() ;
        int[] a = nia(n)  ;
        
        init(n,a);
        for(int i=0;i<m;i++){
            int t = ni();
            int l = ni();
            int r = ni();
            if(t==1){
                updateRange(l-1,r,1,0,N);
                //for(int j=N;j<2*N;j++)
                //    System.out.print(j-N!=N-1?sTree[j].sum+" ":sTree[j].sum+"\n");
            }if(t==2){
                pl(count(l-1,r,1,0,N));
            }
        }
        flush();
        
   }
    
    
    ////////////////////////////////////////////////////////////////////////////////    
    
    private static final byte[] buffer = new byte[1024];
	private static int ptr = 0;
	private static int buflen = 0;
	private static boolean hasNextByte() {
		if (ptr < buflen)  return true;
		else{
			ptr = 0;
			try {
				buflen = System.in.read(buffer);
			} catch (IOException e) {e.printStackTrace();}
			if (buflen <= 0)  return false;
		}
		return true;
	}
	private static int readByte() { return hasNextByte() ? buffer[ptr++] : -1;}
	private static boolean isPrintableChar(int c) { return 33 <= c && c <= 126;}
	private static void skipUnprintable() { while(hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++;}
	public static boolean hasNext() { skipUnprintable(); return hasNextByte();}
	public static String next() {
		if (!hasNext()) throw new NoSuchElementException();
		StringBuilder sb = new StringBuilder();
		for(int b = readByte();isPrintableChar(b);b = readByte()) {
			sb.appendCodePoint(b);
		}
		return sb.toString();
	}
	public static int nextInt() {return (int)nextLong();}
	public static long nextLong() {
		if (!hasNext()) throw new NoSuchElementException();
		long n = 0;
		boolean minus = false;
		int b = readByte();
		if (b == '-') {
			minus = true;
			b = readByte();
		}
		if (b < '0' || '9' < b)  throw new NumberFormatException();
		while(true){
			if ('0' <= b && b <= '9') n = n * 10 + b-'0';
			else if(b == -1 || !isPrintableChar(b)) return minus ? -n : n;
			else throw new NumberFormatException();
			b = readByte();
		}
	}
	public static long[] nextLongArray(int i){
		long[] result=new long[i];
		for(int j=0;j<i;j++)  result[j]=nextLong();
		return result;
	}
	public static void nextLongArray(long[]... arrays){
		for(int j=0;j<arrays[0].length;j++)
			for(long[] array:arrays) array[j]=nextLong();
	}
	public static int[] nextIntArray(int i){
		int[] result=new int[i];
		for(int j=0;j<i;j++)  result[j]=nextInt();
		return result;
	}
	public static void nextIntArray(int[]... arrays){
		for(int j=0;j<arrays[0].length;j++)
			for(int[] array:arrays)  array[j]=nextInt();
	}
	public static int ni(){return nextInt();}
	public static long nl(){return nextLong();}
	public static int[] nia(int n){return nextIntArray(n);}
	public static long[] nla(int n){return nextLongArray(n);}
	public static String ne(){return next();}
	
	static StringBuilder sb=new StringBuilder();
	public static void flush(){
		System.out.print(sb);
		sb=new StringBuilder();
	}
	public static void pr(Object o){sb.append(o);}
	public static void pl(Object o){sb.append(o).append("\n");}
	public static void pl(){sb.append("\n");}
    
}