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 {
	public static void main(String[] args) {new F();}

	F () {
		FastScanner fs = new FastScanner();
		PrintWriter out = new PrintWriter(System.out);
		System.err.println("Go!");
		
		int max = (int)1e6+1;
		int[] div = new int[max];
		for(int i = 1; i < max; i++)
			for(int j = i; j < max; j += i)
				div[j]++;

		int n = fs.nextInt();
		int m = fs.nextInt();
		int[] a = fs.nextIntArray(n);
		Fenwick_Tree ft = new Fenwick_Tree(n);
		for(int i = 0; i < n; i++)
			ft.update(i+1, a[i]);
		TreeSet<Integer> avail = new TreeSet<>();
		for(int i = 0; i < n; i++)
			if(a[i] > 2) avail.add(i);
		
		while(m-->0) {
			int type = fs.nextInt();
			int l = fs.nextInt()-1, r = fs.nextInt()-1;
			if(type == 2) {
				out.println(ft.query(l+1, r+1));
			}
			else {
				Integer next = l;
				while((next = avail.ceiling(next)) != null) {
					if(next > r) break;
					int old = a[next];
					a[next] = div[a[next]];
					if(a[next] < 3) {
						avail.remove(next);
					}
					ft.update(next+1, -old); ft.update(next+1, a[next]);
					next++;
				}
			}
		}
		

		out.close();

	}

	class Fenwick_Tree {

		long[] bit;
		int n;

		public Fenwick_Tree(int a) {
			n = a + 1;
			bit = new long[n];
		}

		//Remember that when querying a sum to query the 1-based index of the value.

		void update (int index, int val) {
			while(index < n) {
				bit[index] += val;
				index += (index & (-index));
			}
		}

		long query(int i, int j) {
			long sum = sum(j);
			if(i > 0) sum -= sum(i-1);
			return sum;
		}

		long sum (int index) {
			long sum = 0;
			while(index > 0) {
				sum += bit[index];
				index -= (index & (-index));
			}
			return sum;
		}
	}

	void sort (long[] a) {
		int n = a.length;
		for(int i = 0; i < 1000; i++) {
			Random r = new Random();
			int x = r.nextInt(n), y = r.nextInt(n);
			long temp = a[x];
			a[x] = a[y];
			a[y] = temp;
		}
		Arrays.sort(a);
	}

	void sort (int[] a) {
		int n = a.length;
		for(int i = 0; i < 1000; i++) {
			Random r = new Random();
			int x = r.nextInt(n), y = r.nextInt(n);
			int temp = a[x];
			a[x] = a[y];
			a[y] = temp;
		}
		Arrays.sort(a);
	}

	class FastScanner {
		BufferedReader br;
		StringTokenizer st;
		public FastScanner() {
			try	{
				br = new BufferedReader(new InputStreamReader(System.in));
				//                br = new BufferedReader(new FileReader("testdata.out"));
				st = new StringTokenizer("");
			} catch (Exception e){e.printStackTrace();}
		}
		public String next() {
			if (st.hasMoreTokens())	return st.nextToken();
			try {st = new StringTokenizer(br.readLine());}
			catch (Exception e) {e.printStackTrace();}
			return st.nextToken();
		}
		public int nextInt() {return Integer.parseInt(next());}
		public long nextLong() {return Long.parseLong(next());}
		public double nextDouble() {return Double.parseDouble(next());}

		public String nextLine() {
			String line = "";
			try {line = br.readLine();}
			catch (Exception e) {e.printStackTrace();}
			return line;
		}
		public Integer[] nextIntegerArray(int n) {
			Integer[] a = new Integer[n];
			for(int i = 0; i < n; i++) a[i] = nextInt();
			return a;
		}
		public int[] nextIntArray(int n) {
			int[] a = new int[n];
			for(int i = 0; i < n; i++) a[i] = nextInt();
			return a;
		}
		public char[] nextCharArray() {return nextLine().toCharArray();}
	}

}