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 CF920_D12_F{
	public static void main(String[] args)throws Throwable {
		MyScanner sc=new MyScanner();
		PrintWriter pw=new PrintWriter(System.out);
		
		int max=(int)(1e6+5);
		int [] c=new int [max];
		for(int i=1;i<max;i++)
			for(int j=i;j<max;j+=i)
				c[j]++;
		
		int n=sc.nextInt();
		int q=sc.nextInt();
		N=1;
		while(N<n) N<<=1;
		a=new int [N+1];
		for(int i=1;i<=n;i++)
			a[i]=sc.nextInt();
		st=new long [N<<1];
		build();
		TreeSet<Integer> set=new TreeSet<Integer>();
		for(int i=1;i<=n;i++)
			if(a[i]>2)
				set.add(i);
		while(q-->0){
			int t=sc.nextInt();
			int l=sc.nextInt();
			int r=sc.nextInt();
			if(t==2)
				pw.println(query(l, r));
			else{
				ArrayList<Integer> rem=new ArrayList<Integer>();
				for(int i : set.subSet(l, r+1)){
					int oldV=a[i];
					int newV=c[a[i]];
					update_point(i, newV-oldV);
					a[i]=newV;
					if(newV<=2)
						rem.add(i);
				}
				for(Integer i : rem)
					set.remove(i);
			}
		}
		
		pw.flush();
		pw.close();
	}
	
	static class pair implements Comparable<pair>{
		int idx,val;
		pair(int i,int v){
			idx=i;
			val=v;
		}
		public int compareTo(pair o) {
			if(idx!=o.idx)
				return idx-o.idx;
			return val-o.val;
		}
		public String toString(){
			return idx+"-> "+val;
		}
		
	}
	
	static int N;
	static long [] st;
	static int [] a;
	
	static void build(){
		build(1,N,1);
	}
	
	static long build(int s,int e,int p){
		if(s==e)
			return st[p]=a[s];
		else
			return st[p]=build(s, (s+e)/2, 2*p)+build((s+e)/2+1, e, 2*p+1);
	}
	
	static void update_point(int idx,int val){
		idx+=N-1;
		st[idx]+=val;
		while(idx>1){
			idx/=2;
			st[idx]=st[2*idx]+st[2*idx+1];
		}
	}
	
	static long query(int i,int j){
		return query(1,N,1,i,j);
	}
	
	static long query(int s,int e,int p,int i,int j){
		if(j<s || i>e)
			return 0;
		if(s>=i && e<=j)
			return st[p];
		long q1=query(s, (s+e)/2, 2*p, i, j);
		long q2=query((s+e)/2+1, e, 2*p+1, i, j);
		return q1+q2;
	}
	
	static class MyScanner {
		BufferedReader br;
		StringTokenizer st;
		public MyScanner() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}
		String next() {while (st == null || !st.hasMoreElements()) {
			try {st = new StringTokenizer(br.readLine());}
			catch (IOException e) {e.printStackTrace();}}
		return st.nextToken();}
		int nextInt() {return Integer.parseInt(next());}
		long nextLong() {return Long.parseLong(next());}
		double nextDouble() {return Double.parseDouble(next());}
		String nextLine(){String str = "";
		try {str = br.readLine();}
		catch (IOException e) {e.printStackTrace();}
		return str;}
	}
}