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:
/* Author: Ronak Agarwal, reader part not written by me*/
import java.io.* ; import java.util.* ;
import static java.lang.Math.min ; import static java.lang.Math.max ;
import static java.lang.Math.abs ; import static java.lang.Math.log ;
import static java.lang.Math.pow ; import static java.lang.Math.sqrt ;
/* Thread is created here to increase the stack size of the java code so that recursive dfs can be performed */
public class F{
	public static void main(String[] args) throws IOException{
		new Thread(null,new Runnable(){	public void run(){ exec_Code() ;} },"Solver",1l<<27).start() ;
	}
	static void exec_Code(){
		try{
			Solver Machine = new Solver() ;
			Machine.Solve() ; Machine.Finish() ;}
		catch(Exception e){ e.printStackTrace() ; print_and_exit() ;}
		catch(Error e){ e.printStackTrace() ; print_and_exit() ; }
	}
	static void print_and_exit(){ System.out.flush() ; System.exit(-1) ;}
}
/* Implementation of the Reader class */
class Reader { 
	private InputStream mIs;
	private byte[] buf = new byte[1024];
	private int curChar,numChars;
	public Reader() { this(System.in); } 
	public Reader(InputStream is) { mIs = is;} 
	public int read() {
		if (numChars == -1) throw new InputMismatchException();    
		if (curChar >= numChars) {
			curChar = 0;
			try { numChars = mIs.read(buf);} catch (IOException e) { throw new InputMismatchException();}
			if (numChars <= 0) return -1;            
		}
		return buf[curChar++];
	} 
	public String nextLine(){
		int c = read();
		while (isSpaceChar(c)) c = read();        
		StringBuilder res = new StringBuilder();
		do {
			res.appendCodePoint(c);
			c = read();
		} while (!isEndOfLine(c));
		return res.toString() ;
	} 
	public String s(){
		int c = read();
		while (isSpaceChar(c)) c = read();        
		StringBuilder res = new StringBuilder();
		do {
			res.appendCodePoint(c);
			c = read();
		}while (!isSpaceChar(c));
		return res.toString();
	} 
	public long l(){
		int c = read();
		while (isSpaceChar(c)) c = read();        
		int sgn = 1;
		if (c == '-') { sgn = -1 ; c = read() ; }
		long res = 0;
		do{
			if (c < '0' || c > '9') throw new InputMismatchException();
			res *= 10 ; res += c - '0' ; c = read();
		}while(!isSpaceChar(c));
		return res * sgn;
	} 
	public int i(){
		int c = read() ;
		while (isSpaceChar(c)) c = read();        
		int sgn = 1;
		if (c == '-') { sgn = -1 ; c = read() ; }
		int res = 0;
		do{
			if (c < '0' || c > '9') throw new InputMismatchException();
			res *= 10 ; res += c - '0' ; c = read() ;
		}while(!isSpaceChar(c));
		return res * sgn;
	} 
	public boolean isSpaceChar(int c) { return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1; } 
	public boolean isEndOfLine(int c) { return c == '\n' || c == '\r' || c == -1; } 
}   
/* All the useful functions,constants,renamings are here*/
class Template{
	/* Constants Section */
	final int INT_MIN = Integer.MIN_VALUE ; final int INT_MAX = Integer.MAX_VALUE ;
	final long LONG_MIN = Long.MIN_VALUE ; final long LONG_MAX = Long.MAX_VALUE ;
	static long MOD = 1000000007 ;
	static Reader ip = new Reader() ;	
	static PrintWriter op = new PrintWriter(System.out) ;
	/* Methods for writing */
	static void p(Object o){ op.print(o) ; }
	static void pln(Object o){ op.println(o) ;}
	static void Finish(){ op.flush(); op.close(); }
	/* Implementation of operations modulo MOD */
	static long inv(long a){ return powM(a,MOD-2) ; }
	static long m(long a,long b){ return (a*b)%MOD ; }
	static long d(long a,long b){ return (a*inv(b))%MOD ; }
	static long powM(long a,long b){
		if(b<0) return powM(inv(a),-b) ;
		long ans=1 ;
		for( ; b!=0 ; a=(a*a)%MOD , b/=2) if((b&1)==1) ans = (ans*a)%MOD ;
		return ans ;
	}
	/* Renaming of some generic utility classes */
	final static class mylist extends ArrayList<Integer>{}
	final static class myset extends TreeSet<Integer>{}
	final static class mystack extends Stack<Integer>{}
	final static class mymap extends TreeMap<Integer,Integer>{}
}
/* Implementation of the pair class, useful for every other problem */
class pair implements Comparable<pair>{
	int x ; int y ;
	pair(int _x,int _y){ x=_x ; y=_y ;} 
	public int compareTo(pair p){
		return (this.x<p.x ? -1 : (this.x>p.x ? 1 : (this.y<p.y ? -1 : (this.y>p.y ? 1 : 0)))) ;
	}
}
/* Main code starts here */
class Solver extends Template{
	int MAXN = 1000000 ;
	int nd[] = new int[MAXN+1] ;
	int fac[] = new int[MAXN+1] ;
	void Fill(){
		for(int i=1 ; i<=MAXN ; i++) fac[i] = i ;
		for(int i=2 ; i<=MAXN ; i++)
			if(fac[i]==i)
				for(int j=(2*i) ; j<=MAXN ; j+=i)
					fac[j] = i ;
		nd[1] = 1 ;
		for(int i=2 ; i<=MAXN ; i++){
			int ct=1 ;
			int j = i ; int prm = fac[i] ;
			while(j%prm==0){j/=prm ; ct++ ;}
			nd[i] = ct*nd[j] ;
		}
	}
	int LM = 7 ;
	long seg[][] ;
	int lz[] ;
	int a[][] ;
	void build(int i,int s,int e){
		if(s==e){
			for(int j=0 ; j<=LM ; j++) seg[j][i] = a[j][s] ;
			return ;
		}
		int m = (s+e)/2 ;
		build(i+i,s,m) ; build(i+i+1,m+1,e) ;
		for(int j=0 ; j<=LM ; j++) seg[j][i] = seg[j][i+i]+seg[j][i+i+1] ;
	}
	void rLaz(int i,int s,int e){
		if(lz[i]!=0){
			int k = lz[i] ;
			for(int j=0 ; j<=LM ; j++){
				if((j+k)<=LM) seg[j][i] = seg[j+k][i] ;
				else seg[j][i] = (e-s+1)*2 ; 
			}
			if(s!=e){
				lz[i+i]+=k ;
				lz[i+i+1]+=k ;
			} 
			lz[i]=0 ;
		}
	}
	void upd(int i,int s,int e,int l,int r){
		rLaz(i,s,e) ;
		if(r<s || e<l) return ;
		if(l<=s && e<=r){
			lz[i]++ ; rLaz(i,s,e) ;
			return ;
		}
		int m = (s+e)/2 ;
		upd(i+i,s,m,l,r) ; upd(i+i+1,m+1,e,l,r) ;
		for(int j=0 ; j<=LM ; j++) seg[j][i] = seg[j][i+i]+seg[j][i+i+1] ;
	}
	long qry(int i,int s,int e,int l,int r){
		rLaz(i,s,e) ;
		if(r<s || e<l) return 0 ;
		if(l<=s && e<=r) return seg[0][i] ;
		int m = (s+e)/2 ;
		return qry(i+i,s,m,l,r)+qry(i+i+1,m+1,e,l,r) ;
	}
	public void Solve() throws IOException{
		Fill() ;
		int n = ip.i() ;
		int m = ip.i() ;
		a = new int[LM+1][n+1] ;
		int ct1[] = new int[n+1] ;
		seg = new long[LM+1][5*n] ;
		lz = new int[5*n] ;
		for(int i=1 ; i<=n ; i++) a[0][i] = ip.i() ;
		for(int i=1 ; i<=n ; i++) ct1[i] = ct1[i-1]+(a[0][i]==1 ? 1 : 0) ;
		for(int i=1 ; i<=n ; i++) if(a[0][i]==1) a[0][i] = 2 ;
		for(int j=1 ; j<=LM ; j++)
			for(int i=1 ; i<=n ; i++)
				a[j][i] = nd[a[j-1][i]] ;
		build(1,1,n) ;
		while(m--!=0){
			int t = ip.i() ; int l = ip.i() ; int r = ip.i() ;
			if(t==1){
				upd(1,1,n,l,r) ;
			}else{
				pln(((qry(1,1,n,l,r)-ct1[r])+ct1[l-1])) ;
			}
		}
	}
}