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:
//package codeforces.Educational37;

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 F_
{
	static int[] div;
	public static void main(String[] args) throws IOException
	{
		Scanner sc = new Scanner(System.in);
		PrintWriter pw = new PrintWriter(System.out);
		
		int n = sc.nextInt();
		int m = sc.nextInt();
		
		int N = 1; while(N < n) N <<= 1; //padding
		
		int[] in = new int[N + 1];
		for(int i = 1; i <= n; i++)
			in[i] = sc.nextInt();
		
		div = new int[1000006];
		Arrays.fill(div, 1);
		for (int step = 2; step < div.length; step++)
			for (int i = step; i < div.length; i+=step)
				div[i]++;
		
		
		SegmentTree t = new SegmentTree(in);
		for (int i = 0; i < m; i++)
		{
			int type = sc.nextInt();
			if(type == 1)
			{
				t.update_range(sc.nextInt(), sc.nextInt(), 0);
			}else
			{
				pw.println(t.query(sc.nextInt(), sc.nextInt()));
			}
		}
		
		pw.flush();
		pw.close();
	}
	
	static class SegmentTree
	{
		int N; 			//the number of elements in the array as a power of 2 (i.e. after padding)
		int[] array;
		long[] sTree;
		boolean[] allOnes;
		
		SegmentTree(int[] in)		
		{
			array = in; N = in.length - 1;
			sTree = new long[N<<1];		//no. of nodes = 2*N - 1, we add one to cross out index zero
			allOnes = new boolean[N<<1];
			build(1,1,N);
		}
		
		void build(int node, int b, int e)	// O(n)
		{
			if(b == e)			
			{
				sTree[node] = array[b];	// modify base case
				if(array[b] == 1 || array[b] == 2)
					allOnes[node] = true;
			}
			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];	// modify merging
				allOnes[node] = allOnes[node<<1] & allOnes[node<<1|1];
			}
		}
		
		
		
		
		void update_range(int i, int j, int val)		// O(log n) 
		{
			update_range(1,1,N,i,j,val);
		}
		
		void update_range(int node, int b, int e, int i, int j, int val)
		{
			if(i > e || j < b)		
				return;
			if(allOnes[node])
				return;
			if(b == e)
			{
				sTree[node] = div[(int)sTree[node]];
				if(sTree[node] == 1 || sTree[node] == 2)
					allOnes[node] = true;
			}
			else
			{
				int mid = b + e >> 1;
				update_range(node<<1,b,mid,i,j,val);
				update_range(node<<1|1,mid+1,e,i,j,val);
				sTree[node] = sTree[node<<1] + sTree[node<<1|1];		// merging
				allOnes[node] = allOnes[node<<1] & allOnes[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)	// O(log n)
		{
			if(i>e || j <b)
				return 0;		// base case 1
			if(b>= i && e <= j)
				return sTree[node];	// base case 2
			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;	// merging
					
		}
		
		
//		public static void main(String[] args) {
//			
//			Scanner sc = new Scanner(System.in);
//			
//			
//		}
		
	}

	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 boolean ready() throws IOException {return br.ready();}
	}
}