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.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Random;
import java.util.StringTokenizer;

public class Solution{
	
	static final int N = (int)1e6+10;
	static int[] D;
	
	
    public static void main(String[] args) throws IOException {
    	
		
    	FastScanner fs = new FastScanner();
    	PrintWriter out = new PrintWriter(System.out);
    		
    	int tt = 1;
    	while(tt-->0) {
    		
    		int n = fs.nextInt(), m = fs.nextInt();
    		int[] a = fs.readArray(n);
    		
    		D = new int[N];
    		
    		for(int i=1;i<N;i++) {
    			for(int j=i;j<N;j+=i) {
    				D[j]++;
    			}
    		}
    		
    		int[] d = D;
    		
    		SegTree tree = new SegTree(n);
    		tree.build(a, 0, n-1, 0);
    		
    		
    		while(m-->0) {
    			int t = fs.nextInt(), l = fs.nextInt()-1, r = fs.nextInt()-1;
    			if(t==1) {
    				tree.update(l, r, 0, n-1, 0);
    			}
    			else {
    				out.println(tree.query(l, r, 0, n-1, 0));
    			}
    		}
    		
    		
    		
    		
    		
    		
    		
    		
    		
    		
    	}
    	
    	out.close();
    		
    }
   
    
    
    
   
    static class SegTree{
    	long[] sTree;
    	int[] max;
    	
    	SegTree(int n){
    		sTree = new long[4*n];
    		max = new int[4*n];
    	}
    	
    	void build(int[] a, int ns, int ne, int node) {
    		if(ns==ne) {
    			sTree[node] = a[ns];
    			max[node] = a[ns];
    			return;
    		}
    		int mid = (ns+ne)/2;
    		build(a, ns, mid, 2*node+1);
    		build(a, mid+1, ne, 2*node+2);
    		sTree[node] = sTree[2*node+1] + sTree[2*node+2];
    		max[node] = Math.max(max[2*node+1], max[2*node+2]);
    	}
    	
    	void update(int l, int r, int ns, int ne, int node) {
    		if(max[0]>2)
    			rangeUpdate(l, r, ns, ne, node);
    	}
    	
    	void rangeUpdate(int l, int r, int ns, int ne, int node) {
    		if(ns>r || ne<l) return;
    		if(ns==ne) {
    			int val = D[(int)sTree[node]];
    			sTree[node] = val;
    			max[node] = val;
    			return;
    		}
    		
    		
    		int mid = (ns+ne)/2;
    		if(max[2*node+1]>2)
    			rangeUpdate(l, r, ns, mid, 2*node+1);
    		if(max[2*node+2]>2)
    			rangeUpdate(l, r, mid+1, ne, 2*node+2);
    		
    		sTree[node] = sTree[2*node+1] + sTree[2*node+2];
    		max[node] = Math.max(max[2*node+1], max[2*node+2]);
    		
    	}
    	
    	long query(int qs, int qe, int ns, int ne, int node) {
    		if(ne<qs || ns>qe) return 0;
    		if(ns>=qs && ne<=qe) return sTree[node];
    		int mid = (ns+ne)/2;
    		return query(qs, qe, ns, mid, 2*node+1) + query(qs, qe, mid+1, ne, 2*node+2);
    	}
    	
    }
    

   
   
    
    
    static final Random random=new Random();
    
    static <T> void shuffle(T[] arr) {
    	int n = arr.length;
    	for(int i=0;i<n;i++	) {
    		int k = random.nextInt(n);
    		T temp = arr[k]; arr[k] = arr[i]; arr[i] = temp;
    	}
    }
    
    	
    static void ruffleSort(int[] a) {
    	int n=a.length;//shuffle, then sort 
    	for (int i=0; i<n; i++) {
    		int oi=random.nextInt(n); int temp=a[oi];
    		a[oi]=a[i]; a[i]=temp;
    	}
    	Arrays.sort(a);
    }
    
    static void ruffleSort(long[] a) {
    	int n=a.length;//shuffle, then sort 
    	for (int i=0; i<n; i++) {
    		int oi=random.nextInt(n); long temp=a[oi];
    		a[oi]=a[i]; a[i]=temp;
    	}
    	Arrays.sort(a);
    }
   
  
    
    static void reverse(int[] arr, int l, int r) {
    	for(int i=l;i<l+(r-l)/2;i++){
    		int temp = arr[i]; arr[i] = arr[r-i+l-1]; arr[r-i+l-1] = temp;
    	}
    }
    
    static void reverse(long[] arr, int l, int r) {
    	for(int i=l;i<l+(r-l)/2;i++){
    		long temp = arr[i]; arr[i] = arr[r-i+l-1]; arr[r-i+l-1] = temp;
    	}
    }
    
    
    static <T> void reverse(T[] arr, int l, int r) {
    	for(int i=l;i<l+(r-l)/2;i++) {
    		T temp = arr[i]; arr[i] = arr[r-i+l-1]; arr[r-i+l-1] = temp;
    	}
    }
    	
    	
    static class FastScanner{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	StringTokenizer st = new StringTokenizer("");
     
    	public String next(){
    		while(!st.hasMoreElements()){
    			try{
    				st = new StringTokenizer(br.readLine());
    			} catch(IOException e){
    				e.printStackTrace();
    			}
    		}
    		return st.nextToken();
    	}
    		
    	public String nextLine() throws IOException {
    		return br.readLine();
    	}
    		
    	public int nextInt(){
    		return Integer.parseInt(next());
    	}
     
    	public int[] readArray(int n){
    		int[] a = new int[n];
    		for(int i=0;i<n;i++)
    			a[i] = nextInt();
    		return a;
    	}
    		
    	public long nextLong() {
    		return Long.parseLong(next());
    	}
    		
    	public char nextChar() {
    		return next().toCharArray()[0];
    	}
    }
   	
}