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.*;


public class Main {
    long[]lo,hi,sum,max,D;
    public Main(int arr[]){
        int n=arr.length;
        lo=new long[4*n+1];
        hi=new long[4*n+1];
        max=new long[4*n+1];
        sum=new long[4*n+1];
        D=new long[1000002];
        D();
        init(1,0,n-1,arr);
        
    }
    public void D(){
        int n=1000002;
        for(int i=1;i<n;i++){
            for(int j=i;j<n;j+=i){
                D[j]++;
            }
        }
    }
    public void init(int i,int l,int r,int arr[]){
        lo[i]=l;
        hi[i]=r;
        if(l==r){
            sum[i]=arr[l];
            max[i]=arr[r];
            return;
        }
        int m=(l+r)/2;
        init(2*i,l,m,arr);
        init(2*i+1,m+1,r,arr);
        sum[i]=sum[2*i]+sum[2*i+1];
        max[i]=Math.max(max[2*i], max[2*i+1]);
    }
    public void update(int i,int l,int r){
        if(max[i]<3)return;
        if(lo[i]>r||hi[i]<l)return;
        
        if(lo[i]==hi[i]){
            sum[i]=D[(int)sum[i]];
            max[i]=D[(int)max[i]];
            return;
        }
        update(2*i,l,r);
        update(2*i+1,l,r);
        sum[i]=sum[2*i+1]+sum[2*i];
        max[i]=Math.max(max[2*i], max[2*i+1]);
    }
    public long sum(int i,int l,int r){
        if(lo[i]>r || hi[i]<l)return 0;
        if(lo[i]>=l && hi[i]<=r)return sum[i];
        return sum(2*i,l,r)+sum(2*i+1,l,r);
    }
    
    public static void main(String[] args) throws IOException {
        FastScanner sc=new FastScanner(System.in);
        StringBuilder ans=new StringBuilder();
        int n=sc.nextInt();
        int m=sc.nextInt();
        int a[]=new int[n];
        for(int i=0;i<n;i++)a[i]=sc.nextInt();
        Main s=new Main(a);
        
        for(int i=0;i<m;i++){
            int t=sc.nextInt();
            int l=sc.nextInt()-1;
            int r=sc.nextInt()-1;
            switch(t){
                case 1:
                    s.update(1, l, r);
                    break;
                case 2:
                    ans.append(s.sum(1, l, r)+"\n");
                    break;
            }
        }
        System.out.print(ans.toString());
    
    }
    
    static class FastScanner {
	    BufferedReader br;
	    StringTokenizer st;
            public FastScanner(InputStream i) {
	        br =  new BufferedReader(new InputStreamReader(i));
	        st = new StringTokenizer("");
	    }
	    public String next() throws IOException {
	        if(st.hasMoreTokens())return st.nextToken();
                else st = new StringTokenizer(br.readLine());
	        return next();
	    }
	    public int nextInt() throws IOException {return Integer.parseInt(next());}
	    public long nextLong() throws IOException {return Long.parseLong(next());}
	    public double nextDouble() throws IOException {return Double.parseDouble(next());}
	}
}