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.*;
import java.util.*;
     
public class Solution {
      private static int[] primes;
      private static int[] parent;
      private static long[] st;
      private static int[] last;
      private static boolean[] visited;
      private static final int max = 1000005;
    	 
    public static void main(String[] args) throws Exception{ 
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(System.out);
        primes = new int[max];
        
        computePrimeFactors();
        
       // for(int i=1;i<=20;i++)System.out.println("primeFactors are"+" "+primes[i]);
        
        StringTokenizer tokenizer = new StringTokenizer(br.readLine());
        int n  = Integer.parseInt(tokenizer.nextToken());
        int q = Integer.parseInt(tokenizer.nextToken());
        
        int[] a = new int[n];
        
        tokenizer = new StringTokenizer(br.readLine());
        
        for(int i=0;i<n;i++) 
          a[i] = Integer.parseInt(tokenizer.nextToken());
        
        // Initializing segment tree   
        int x = (int) (Math.ceil(Math.log(n) / Math.log(2))); 
        int max_size = 2 * (int) Math.pow(2, x) - 1; 
        st = new long[max_size]; 
        constructST(a, 0, n - 1, 0); 
        
        // initializing union find
        parent = new int[n];
        last = new int[n];
        for(int i=0;i<n;i++){
             parent[i] = i;
             last[i] = i;
        }
        visited = new boolean[n];
        
        for(int i=0;i<q;i++){
            tokenizer = new StringTokenizer(br.readLine());
            int t= Integer.parseInt(tokenizer.nextToken());
            int l = Integer.parseInt(tokenizer.nextToken())-1;
            int r= Integer.parseInt(tokenizer.nextToken())-1;
            // update case
            if(t == 1){
                 int low = -1;
                 while(l <= r){
                      if(visited[l]){
                           if(low != -1){
                                // creates a new union of this array as well as it checks if
                                // we can find more unions
                                // no need to set visited
                        	   
                                newUnion(low,l-1,n);
                        	   
                             // completed with the union
                                low = -1;
                           }
                           int left = findParent(l);
                           l = last[left]+1;
  
                      }
                      // no unions so far
                      else{
                           // terminal states, update low
                           // be sure to increment l
                         if(a[l] == 1 || a[l] == 2){
                            if(low == -1)
                                low = l;
                            visited[l] = true;
                            l++;
                          }
                          // cases where we need to update the segment tree
                          else{
                               if(low != -1){
                                  // creates a new union of this array as well as it checks if
                                 // we can find more unions
                            	   
                                 newUnion(low,l-1,n);  
                            	   
                                 // completed with the union
                                 low = -1;
                               }
                               // update a[i] and segment tree value
                               int divisors = findDivisors(a[l]);
                               //int divisors = 2;
                               updateValue(a,n,l,divisors);
                               l++;
                          }
                      }   
                 }
                 if(low != -1)
               	  newUnion(low,r,n);
            }
            else{
               long sum = getSum(n,l,r);
                out.println(sum);
            }
        }
         
         out.close();
     }
     
     private static void newUnion(int low, int high,int n){
          for(int i=low+1;i<=high;i++)
             union(low,i);
           
           // joining the left array
           if(low>0 && visited[low-1]){
                union(low-1,low);
           }
           
           if(high < n-1 && visited[high+1]){
                union(high,high+1);
           }
     }
     
     // Finding divisors and sieve of Erasthenos starts from here
     private static void computePrimeFactors(){
          for(int i=0;i<primes.length;i++)
            primes[i] = i;
          
          for(int p=2;p*p<max;p++){
               if(primes[p] == p){
                    for(int i=p*2;i<max;i+=p)
                     primes[i] = Math.min(primes[i],p);
               }
          }
     }
     
     // don't call this method when  n == 1 or n == 2
     private static int findDivisors(int n){
        int divisors = 1;
        while(n > 1){
             int count = 0;
             int fact = primes[n];
             while( n > 1 && n%fact == 0){
                  count++;
                  n/=fact;
             }
             divisors*=(count+1);
        }
        return divisors;
     }
     
     // Union find starts from here
    private static int findParent(int u){
       if(parent[u] == u) return u;
           return  parent[u] = findParent(parent[u]);
    }
    
    // index vise u < v, so u should be the parent  
     private static void union(int u,int v){
         int p1 = findParent(u);
         int p2 = findParent(v);
         parent[p2] = p1;
         last[p1] = last[p2];
     }
    
    
    // segment Tree starts from here
    private static int getMid(int s, int e) { 
        return s + (e - s) / 2; 
    } 
  
    private static long getSumUtil(int ss, int se, int qs, int qe, int si) 
    { 

        if (qs <= ss && qe >= se) 
            return st[si]; 

        if (se < qs || ss > qe) 
            return 0; 

        int mid = getMid(ss, se); 
        return getSumUtil(ss, mid, qs, qe, 2 * si + 1) + 
                getSumUtil(mid + 1, se, qs, qe, 2 * si + 2); 
    } 
  
    private static void updateValueUtil(int ss, int se, int i, long diff, int si) 
    { 

        if (i < ss || i > se) 
            return; 

        st[si] = st[si] + diff; 
        if (se != ss) { 
            int mid = getMid(ss, se); 
            updateValueUtil(ss, mid, i, diff, 2 * si + 1); 
            updateValueUtil(mid + 1, se, i, diff, 2 * si + 2); 
        } 
    } 
  
    private static void updateValue(int arr[], int n, int i, int new_val) 
    { 
        if (i < 0 || i > n - 1) { 
            return; 
        } 

        long diff = new_val - arr[i]; 
        arr[i] = new_val; 
        updateValueUtil(0, n - 1, i, diff, 0); 
    } 
  
    private static long getSum(int n, int qs, int qe) 
    { 
        if (qs < 0 || qe > n - 1 || qs > qe) { 
            return -1; 
        } 
        return getSumUtil(0, n - 1, qs, qe, 0); 
    } 
  
    private static long constructST(int arr[], int ss, int se, int si) 
    { 
        if (ss == se) { 
            st[si] = arr[ss]; 
            return arr[ss]; 
        } 
        int mid = getMid(ss, se); 
        st[si] = constructST(arr, ss, mid, si * 2 + 1) + 
                 constructST(arr, mid + 1, se, si * 2 + 2); 
        return st[si]; 
    } 
}