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:
/* package codechef; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */



public class Codechef
{
    static long seg[];static boolean one2[];
    static int a[];
    static int div[];
    static int n;
    
    static class Input {
        private StringTokenizer tokenizer = null;
        private BufferedReader reader;

        public Input(InputStream inputStream) {
            reader = new BufferedReader(new InputStreamReader(inputStream));
        }

        public String nextLine() {
            try {
                return reader.readLine();
            } catch (IOException e) {
                throw new RuntimeException();
            }
        }

        public String nextToken() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                tokenizer = new StringTokenizer(nextLine());
            }
            return tokenizer.nextToken();
        }

        public int nextInt() {
            return Integer.parseInt(nextToken());
        }

        public int[] nextIntArray(int n, int add) {
            int[] result = new int[n];
            for (int i = 0; i < n; i++) {
                result[i] = nextInt() + add;
            }
            return result;
        }

        public int[] nextIntArray(int n) {
            return nextIntArray(n, 0);
        }

    }

    
    
    
    public static void build(int ss,int se,int si)
    {
        //System.out.println(ss+" "+se+" "+si);
        if(ss==se)
        {seg[si]=a[ss];
         one2[si]=a[ss]<=2;
         return;
        }
        int mid=(ss+se)/2;
        build(ss,mid,si*2);
        build(mid+1,se,si*2+1);
        seg[si]=seg[si*2]+seg[si*2+1];
        one2[si]=one2[si*2] & one2[si*2+1];
    }
    
    public static long getsum(int ss,int se,int l,int r,int si)
    {
        if(l<=0 || r>n || l>r)
        return 0;
        if(l<=ss && r>=se)
        return seg[si];
        
        if(ss>r || se<l)
        return 0;
        
        long sum=getsum(ss,(ss+se)/2,l,r,si*2)+getsum((ss+se)/2+1,se,l,r,si*2+1);
        return sum;
    }
    
    public static void update(int ss,int se,int l,int r,int si)
    {
        if(r<ss || l>se)
        return;
        if(ss==se)
        {
            one2[si]=seg[si]<=2;
            if(one2[si])
            return;
            
            seg[si]=div[(int)seg[si]];
            return;
        }
        
        if(one2[si])
        return;
       // System.out.println(seg[si]+" "+diff);
        
        update(ss,(ss+se)/2,l,r,si*2);
        update((ss+se)/2+1,se,l,r,si*2+1);
        seg[si]=seg[si*2]+seg[si*2+1];
        one2[si]=one2[si*2] & one2[si*2+1];
    }
    
	public static void main (String[] args) throws java.lang.Exception
	{
		Input s=new Input(System.in);
		PrintWriter out=new PrintWriter(System.out);
		 n=s.nextInt();
		int m=s.nextInt();
		 a=new int[n+1];
		 int size=(int)1e6;
		 div=new int[size+1];
	
	    for(int i=1;i<=size;i++)
	    {
	        //div[i]++;
	        for(int j=i;j<=size;j+=i)
	        div[j]++;
	    }
	   
	
		for(int i=1;i<=n;i++)
		a[i]=s.nextInt();
		 int temp = (int)Math.ceil(Math.log(n)/Math.log(2));
            int sss = 2*(int)Math.pow(2,temp)-1;
            //check = new long[n];//System.out.println(l);
		seg=new long[sss+1];
		one2=new boolean[sss+1];
		build(1,n,1);
		
		for(int i=0;i<m;i++)
		{
		    if(s.nextInt()==1)
		    {
                int l=s.nextInt();
                int r=s.nextInt();
                update(1,n,l,r,1);
		    }
		    else
		    {
		       out.println(getsum(1,n,s.nextInt(),s.nextInt(),1));
		    }
		}
		out.flush();
	}
}