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.InputStream;
import java.io.InputStreamReader;
import java.util.Scanner;
import java.util.StringTokenizer;

public class Main {
	
	 static long tree[];static int mx[],ar[];
	 static int[] div;
	 static int a,b,c,n,m,mid;
	 static int max(int a,int b)
	 {
		 if(a>b) return a; 
		 else return b;
	 }
	 public static void insert(int idx,int st,int end)
	 {
		 
		 if(st>end)  return;
		 if(st==end)
		 {
			 tree[(int) idx]=ar[(int) st];
			 mx[(int) idx]=(int) ar[(int) st];
			 return ;
		 }
		  int mid=(st+end)/2;
		  int lf=idx*2;
		  int rg=lf+1;
		 insert(lf,st,mid); 
		 insert(rg,mid+1,end);
		 tree[(int) idx]=tree[(int) lf]+tree[(int) rg];
		 mx[(int) idx]=max(mx[(int) lf],mx[(int) (lf+1)]); 
	 }
	 public static void update(int idx,int st,int end,int i,int j)
	 { 
		// if(st>j ||   end<i)  return;
		 
		 if(st==i && end==j)
		 {
			 
			 if(mx[idx]<=2)  return;

		 }
		 if(st==end)
		 {
			 ar[(int) st]=div[(int) ar[(int) st]];
			 tree[(int) idx]=ar[(int) st ];
			 mx[(int) idx]=(int) ar[(int) st];
			 return ;
		 }
		  int  mid=(st+end)/2;		
			int lf=idx*2;
			
			
			if(j<=mid)    update(lf,st,mid,i,j);
			else if(i>mid)   update(lf+1,mid+1,end,i,j);
			else
			{
				update(lf,st,mid,i,mid);
				update(lf+1,mid+1,end,mid+1,j);
				//return (aa+bb);
			}
		 tree[(int) idx]=tree[(int) lf]+tree[(int) (lf+1)];
		 mx[(int) idx]=max(mx[(int) lf],mx[(int) (lf+1)]);
		 return;
	 }
	 
	 
	 public static long query(int idx,int st,int end,int i,int j)
	 {
		 if(st==i && end==j)
		 {
			 return  tree[(int) idx];
		 }
		int  mid=(st+end)/2;		
		int lf=idx*2;
		
		
		if(j<=mid)  return  query(lf,st,mid,i,j);
		else if(i>mid)  return query(lf+1,mid+1,end,i,j);
		else
		{
			long aa=query(lf,st,mid,i,mid);
			long bb=query(lf+1,mid+1,end,mid+1,j);
			return (aa+bb);
		}
		
		//aa

	 }

	public static void main( String  args[])  throws IOException
	{
		
		Scanner scan=new Scanner(System.in);
		div=new int[1000005];
		tree=new long[4000005];
		mx=new int[4000005];
		ar=new int[1000005];
		for(int i=1;i<=1000000;i++)
		{
			for(int j=i;j<=1000000;j+=i)
			{
				div[(int) j]++;
			}
		}
		n=scan.nextInt(); m=scan.nextInt();
		
		
		
		int tot=0;
		for(int i=1;i<=n;i++)
		{
			int aa=scan.nextInt();
			ar[(int) i]=aa;
			
			tot+=aa;
		}
		
		insert(1,1,n);
		while(m>0)
		{
			m--;
			int t;
			t=scan.nextInt();
			int b,c;
			b=scan.nextInt(); 
			c=scan.nextInt();
			if(t==2)
			{
				long result=query(1,1,n,b,c); 
				System.out.println(result);
			}
			else
			{
				update(1,1,n,b,c);
			}
		}
	}
	
	
	
	static class Scanner {
		StringTokenizer st;
		BufferedReader br;

		public Scanner(InputStream s) {
			br = new BufferedReader(new InputStreamReader(s));
		}

		public String next() throws IOException {
			while (st == null || !st.hasMoreTokens())
				st = new StringTokenizer(br.readLine());
			return st.nextToken();
		}

		public int nextInt() throws IOException {
			return Integer.parseInt(next());
		}

		public long nextLong() throws IOException {
			return Long.parseLong(next());
		}

		public String nextLine() throws IOException {
			return br.readLine();
		}

		public double nextDouble() throws IOException {
			return Double.parseDouble(next());
		}

		public boolean ready() throws IOException {
			return br.ready();
		}
	}

}