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

public class SumAndReplace {
static int []div;
	public static void main(String[] args) throws IOException {
		Scanner sc=new Scanner(System.in);
		int maxN=(int)(1e6);
		div=new int [maxN+1];
		for(int i=1;i<=maxN;i++)
			for(int j=i;j<=maxN;j+=i)
				div[j]++;
		
		int n=sc.nextInt(),q=sc.nextInt();
		int []a=new int [n];
		for(int i=0;i<n;i++)
			a[i]=sc.nextInt();
		SegmentTree tree=new SegmentTree(a);
		PrintWriter pw=new PrintWriter(System.out);
		while(q-->0)
		{
			int t=sc.nextInt(),l=sc.nextInt()-1,r=sc.nextInt()-1;
			if(t==1)
			{
				tree.update(l,r,1);
			}
			else
				pw.println(tree.sumQuery(l, r, 1));
		}
		pw.close();
		

	}
	
	static class SegmentTree
	{
		int []max,left,right;
		long []sum;
		
		int []a;
		SegmentTree(int []b)
		{
			a=b;
			int n=a.length;
			
			int size=1;
			for(;size<n;size*=2);
			
			size*=2;
			max=new int [size];
			
			sum=new long[size];
			left=new int [size];
			right=new int [size];
			build(0,n-1,1);
			
		}
		public void build(int l,int r,int idx)
		{
			
			
			if(l==r)
			{
				
					max[idx]=a[l];
					sum[idx]=a[l];
					left[idx]=l;
					right[idx]=l;
				
			}
			else
			{
				
				int mid=(l+r)/2;
				build(l,mid,2*idx);
				build(mid+1,r,2*idx+1);
				sum[idx]=sum[2*idx]+sum[2*idx+1];
				max[idx]=Math.max(max[2*idx], max[2*idx+1]);
				left[idx]=l;
				right[idx]=r;
			}
			
		}
		public long sumQuery(int l,int r,int idx)
		{
			if(left[idx]>r || right[idx]<l)
				return 0;
			long ans=0;
			if(left[idx]>=l && right[idx]<=r)
				return  sum[idx];
			
			ans+= sumQuery(l,r,2*idx);
			ans+=sumQuery(l,r,2*idx+1);
			return ans;
			
		}
		public void update(int l,int r,int idx)
		{
			
			if(left[idx]>r || right[idx]<l ||max[idx]<=2)
				return;
			if(left[idx]==right[idx])
			{
				int tmp=max[idx];
				max[idx]=div[tmp];
				sum[idx]=div[tmp];
			}
			else
			{
				update(l,r,2*idx);
				update(l,r,2*idx+1);
				sum[idx]=sum[2*idx]+sum[2*idx+1];
				max[idx]=Math.max(max[2*idx], max[2*idx+1]);
			}
		}
	}
	static class Scanner
	{
		BufferedReader br;
		StringTokenizer st;
		public Scanner(InputStream s)
		{
			br=new BufferedReader(new InputStreamReader(s));
		}
		public String nextLine() throws IOException
		{
			return br.readLine();
		}
		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 double nextDouble() throws IOException
		{
			return Double.parseDouble(next());
		}
		public boolean ready() throws IOException
		{
			return br.ready();
		}
		
	}
	
}