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 F
{

	static StringBuilder st = new StringBuilder();
	static int [] numOfDivs ; 
	
	public static void main(String[] args) throws Exception 
	{

		Scanner sc = new Scanner(System.in);
		PrintWriter out = new PrintWriter(System.out);
		
		numOfDivs = new int [(int)1e6 + 1] ; 
		
		for(int i = 1 ; i <= 1e6 ; i++)
			for(int j = i ; j <= 1e6 ; j += i)
				numOfDivs[j]++;
		
		int n = sc.nextInt() , m =sc.nextInt();
		
		int N = 1 ; 
		
		while(N < n) N <<= 1 ;
		
		long [] in = new long [N + 1] ; 
		
		for(int i = 1 ; i <= n ; i++) in[i] = sc.nextInt() ; 
		
		SegmentTree tree = new SegmentTree(in);
		
		while(m-->0)
		{
			int t = sc.nextInt() , l = sc.nextInt() , r = sc.nextInt();
			
			if(t == 1)
				tree.update_range(l, r);
			else
				out.println(tree.query(l, r));
			
		}
		
		out.flush();
		out.close();

	}
	
	static class SegmentTree {		
		
		int N; 			
		long[] array, sTree, lazy;
		boolean [] end ; 
		SegmentTree(long[] in)		
		{
			array = in; N = in.length - 1;
			sTree = new long[N<<1];		
			lazy = new long[N<<1];
			end = new boolean [N << 1 ] ; 
			build(1,1,N);
		}
		
		void build(int node, int b, int e)	
		{
			if(b == e)
			{
				sTree[node] = array[b];
				end[node] = array[b] <= 2 ; 
			}
			else						
			{
				int mid = b + e >> 1;
				build(node<<1,b,mid);
				build(node<<1|1,mid+1,e);
				sTree[node] = sTree[node<<1]+sTree[node<<1|1];
				end[node] = end[node << 1] & end[node << 1|1] ; 
			}
		}
		
		void update_range(int i, int j)		
		{
			update_range(1,1,N,i,j);
		}
		
		void update_range(int node, int b, int e, int i, int j)
		{
			if(i > e || j < b || end[node])		
				return;
			
			if(b == e)		
			{
				sTree[node] = numOfDivs[(int)sTree[node]];			
				end[node] = sTree[node] <= 2 ; 
			}							 
			else		
			{
				int mid = b + e >> 1;
				
				update_range(node<<1,b,mid,i,j);
				update_range(node<<1|1,mid+1,e,i,j);
				sTree[node] = sTree[node<<1] + sTree[node<<1|1];		
				end[node] = end[node << 1] & end[node << 1|1] ; 
				
			}
			
		}
		
		long query(int i, int j)
		{
			return query(1,1,N,i,j);
		}
		
		long query(int node, int b, int e, int i, int j)
		{
			if(i>e || j <b)
				return 0;		
			if(b>= i && e <= j)
				return sTree[node];
			
			int mid = b + e >> 1;
			long q1 = query(node<<1,b,mid,i,j);
			long q2 = query(node<<1|1,mid+1,e,i,j);
			return q1 + q2;	
					
		}
	}
	static class Scanner 
	{
		BufferedReader br;
		StringTokenizer st;

		Scanner(InputStream in) 
		{
			br = new BufferedReader(new InputStreamReader(System.in));
		}

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

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

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

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

	}

	static void shuffle(int[] a) {
		int n = a.length;
		for (int i = 0; i < n; i++) {
			int r = i + (int) (Math.random() * (n - i));
			int tmp = a[i];
			a[i] = a[r];
			a[r] = tmp;
		}
	}

}