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.text.*;
public class Main{
    static final long MOD = (long)1e9+7;
    static final int MAX = (int)1e6+1;
    static FastReader in;
    
    static int[] count,A;
    static long[] sum,max;
    public static void main(String[] args){
        in = new FastReader();
        count = new int[MAX];
        for(int i = 1; i< MAX; i++)for(int j = i; j< MAX; j+=i)count[j]++;
        int T = 1;
        StringBuilder out = new StringBuilder("");
        while(T-->0){
            int N = ni(), Q = ni();
            A = new int[N];
            int M = 1;
            while(M<N)M<<=1;
            sum = new long[M<<1]; max = new long[M<<1];
            for(int i = 0; i< N; i++){
                A[i] = ni();
                sum[i+M] = A[i];
                max[i+M] = A[i];
            }
            for(int i = M-1; i> 0; i--){
                sum[i] = sum[i<<1]+sum[i<<1|1];
                max[i] = Math.max(max[i<<1], max[i<<1|1]);
            }
            while(Q-->0){
                int t = ni(), l = ni()-1, r = ni()-1;
                if(t==1){
                    update(0,M-1,l,r,1);
                }else{
                    long ans = 0;
                    for(l+=M, r+=M+1; l<r; l>>=1, r>>=1){
                        if((l&1)==1)ans+=sum[l++];
                        if((r&1)==1)ans+=sum[--r];
                    }
                    out.append(ans+"\n");
                }
            }
        }
        System.out.println(out.toString());
    }
    
    static void update(int L, int R, int l, int r, int i){
        if(max[i]<=2 || R<l || L>r)return;
        if(L==R){
            A[L] = count[A[L]];
            sum[i] = A[L];
            max[i] = A[L];
            return;
        }
        int mid = (L+R)>>1;
        update(L,mid,l,r,i<<1);
        update(mid+1,R,l,r,i<<1|1);
        sum[i] = sum[i<<1]+sum[i<<1|1];
        max[i] = Math.max(max[i<<1], max[i<<1|1]);
    }
    
    static void p(Object o){
        System.out.print(o);
    }
    
    static void pn(Object o){
        System.out.println(o);
    }
    
    static String n(){
        return in.next();
    }
    
    static String nln(){
        return in.nextLine();
    }
    
    static int ni(){
            return Integer.parseInt(in.next());
    }
    
    static long nl(){
        return Long.parseLong(in.next());
    }
    
    static double nd(){
        return Double.parseDouble(in.next());
    }
    
    static class FastReader{
        BufferedReader br;
        StringTokenizer st;
        public FastReader(){
            br = new BufferedReader(new InputStreamReader(System.in));
        }
        
        public FastReader(String s) throws Exception{
            br = new BufferedReader(new FileReader(s));
        }
 
        String next(){
            while (st == null || !st.hasMoreElements()){
                try{
                    st = new StringTokenizer(br.readLine());
                }catch (IOException  e){
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }
 
        String nextLine(){
            String str = "";
            try{
                str = br.readLine();
            }catch (IOException e){
                e.printStackTrace();
            }
            return str;
        }
    }
}