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.util.*;
import java.io.*;
import java.math.BigInteger;

public class Solution {
	
	public static class FastReader {
		 
		private InputStream stream;
		private byte[] buf = new byte[4096];
		private int curChar, snumChars;
 
		public FastReader(InputStream stream) {
			this.stream = stream;
		}
 
		public int read() {
			if (snumChars == -1) {
				throw new InputMismatchException();
			}
			if (curChar >= snumChars) {
				curChar = 0;
				try {
					snumChars = stream.read(buf);
				} catch (IOException E) {
					throw new InputMismatchException();
				}
			}
			if (snumChars <= 0) {
				return -1;
			}
			return buf[curChar++];
		}
 
		public int nextInt() {
			int c = read();
			while (isSpaceChar(c)) {
				c = read();
			}
			int sgn = 1;
			if (c == '-') {
				sgn = -1;
				c = read();
			}
			int number = 0;
			do {
				number *= 10;
				number += c - '0';
				c = read();
			} while (!isSpaceChar(c));
			return number * sgn;
		}
 
		public long nextLong() {
			int c = read();
			while (isSpaceChar(c)) {
				c = read();
			}
			long sgn = 1;
			if (c == '-') {
				sgn = -1;
				c = read();
			}
			long number = 0;
			do {
				number *= 10L;
				number += (long) (c - '0');
				c = read();
			} while (!isSpaceChar(c));
			return number * sgn;
		}
 
		public int[] nextIntArray(int n) {
			int[] arr = new int[n];
			for (int i = 0; i < n; i++) {
				arr[i] = this.nextInt();
			}
			return arr;
		}
 
		public long[] nextLongArray(int n) {
			long[] arr = new long[n];
			for (int i = 0; i < n; i++) {
				arr[i] = this.nextLong();
			}
			return arr;
		}
 
		public String next() {
			int c = read();
			while (isSpaceChar(c)) {
				c = read();
			}
			StringBuilder res = new StringBuilder();
			do {
				res.appendCodePoint(c);
				c = read();
			} while (!isSpaceChar(c));
			return res.toString();
		}
 
		public String nextLine() {
			int c = read();
			while (isSpaceChar(c)) {
				c = read();
			}
			StringBuilder res = new StringBuilder();
			do {
				res.appendCodePoint(c);
				c = read();
			} while (!isEndofLine(c));
			return res.toString();
		}
 
		public boolean isSpaceChar(int c) {
			return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
		}
 
		public boolean isEndofLine(int c) {
			return c == '\n' || c == '\r' || c == -1;
		}
 
	}
 
	public static FastReader sc;
	public static PrintWriter out;
	public static void main(String[] args) {
		new Thread(null, null, "Thread", 1 << 28) {
			public void run() {
				try {
					out = new PrintWriter(new BufferedOutputStream(System.out));
					sc = new FastReader(System.in);
					new Solution().solve();
					out.close();
				} catch (Exception len) {
					len.printStackTrace();
					System.exit(1);
				}
			}
		}.start();
	}
	protected void solve() {
	
		int n = sc.nextInt();
		int q = sc.nextInt();
		int[] a = new int[n+1];
		TreeSet<Integer> set = new TreeSet<>();
		for(int i=1;i<=n;++i) {
			a[i] = sc.nextInt();
			set.add(i);
		}
		int[] d = new int[1000010];
		for(int i=1;i<d.length;++i) {
			for(int j=i;j<d.length;j+=i) d[j]++;
		}
		Fenwick bit = new Fenwick(a);
		while(q-->0) {
			int t = sc.nextInt();
			int l = sc.nextInt();
			int r = sc.nextInt();
		    if(t == 1) {
		    	Integer idx = set.ceiling(l);
		    	while(idx != null && idx <= r) {
		    		bit.update(idx,a[idx],d[a[idx]]);
		    		a[idx] = d[a[idx]];
		    		if(a[idx] <= 2) set.remove(idx);
		    		idx = set.higher(idx);
		    	}
		    }else {
		    	out.println(bit.query(r) - bit.query(l-1));
		    }
		    
		    
		}	
	}
	
	class Fenwick{
		long[] bit;
		Fenwick(int[] a){
			int n = a.length-1;
			bit = new long[n+1];
			for(int i=1;i<=n;++i) update(i,0,a[i]);
		}
		
		long query(int i) {
			long sum = 0;
			while(i > 0) {
				sum+=bit[i];
				i -= -i&i;
			}
			return sum;
		}
		void update(int i, int from,int to) {
			long val = to - from; // change to previous to new value
			int n = bit.length;
			while(i < n) {
				bit[i]+=val;
				i += -i&i;
			}
			
		}
		
	}
	
		

	
}