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

	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 q = sc.nextInt();
		int[] in = new int[n + 1];
		TreeSet<Integer> ts = new TreeSet<>();
		FenwickTree fn = new FenwickTree(n);
		int max = 2;
		for (int i = 1; i <= n; i++) {
			in[i] = sc.nextInt();
			fn.point_update(i, in[i]);
			if (in[i] > 2)
				ts.add(i);
			max = Math.max(max, in[i]);
		}
//        for (int i =2;i<=10;i++){
//            System.out.print(fun[i]+" ");
//        }
//        System.out.println();
		sieve(max);
		ArrayList<Integer> removed = new ArrayList<>();
		while (q-- > 0) {
			if (sc.nextInt() == 2) {
				int l = sc.nextInt();
				int r = sc.nextInt();
				pw.println(fn.rsq(l, r));
			} else {
				int l = sc.nextInt();
				int r = sc.nextInt();
				for (int id : ts.subSet(l, r + 1)) {
					fn.point_update(id, fun[in[id]] - in[id]);
					in[id] = fun[in[id]];
					if (in[id] <= 2)
						removed.add(id);
				}
				for(int x:removed)
					ts.remove(x);
				removed.clear();
			}
		}
		pw.flush();
	}

	static class FenwickTree {
		int n;
		long[] ft;

		FenwickTree(int size) {
			n = size;
			ft = new long[n + 1];
		}

		long rsq(int b) // O(log n)
		{
			long sum = 0;
			while (b > 0) {
				sum += ft[b];
				b -= b & -b;
			} // min?
			return sum;
		}

		long rsq(int a, int b) {
			return rsq(b) - rsq(a - 1);
		}

		void point_update(int k, int val) // O(log n), update = increment
		{
			while (k <= n) {
				ft[k] += val;
				k += k & -k;
			} // min?
		}
	}

	static int[] isComposite, fun;

	static void sieve(int N) {
		isComposite = new int[N + 1];
		fun = new int[N + 1];
		isComposite[0] = isComposite[1] = 1;
		Arrays.fill(fun, 1);
		for (int i = 2; i <= N; i++)
			if (isComposite[i] == 0) {
				fun[i] = 2;
				for (int j = i + i; j <= N; j += i) {
					isComposite[j] = 1;
					int x = j;
					int e = 1;
					while (x % i == 0) {
						x /= i;
						e++;
					}
					fun[j] *= e;
				}
			}
	}

	static long gcd(long a, long b) {
		if (a == 0)
			return b;
		return gcd(b % a, a);
	}

	static int inver(long x, int mod) {
		int a = (int) x;
		int e = (mod - 2);
		int res = 1;
		while (e > 0) {
			if ((e & 1) == 1) {
				// System.out.println(res*a);
				res = (int) ((1l * res * a) % mod);
			}
			a = (int) ((1l * a * a) % mod);
			e >>= 1;
		}
		// out.println(res+" "+x);
		return res % mod;
	}

	static class Scanner {
		StringTokenizer st;
		BufferedReader br;

		public Scanner(FileReader r) {
			br = new BufferedReader(r);
		}

		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 double nextDouble() throws IOException {
			String x = next();
			StringBuilder sb = new StringBuilder("0");
			double res = 0, f = 1;
			boolean dec = false, neg = false;
			int start = 0;
			if (x.charAt(0) == '-') {
				neg = true;
				start++;
			}
			for (int i = start; i < x.length(); i++)
				if (x.charAt(i) == '.') {
					res = Long.parseLong(sb.toString());
					sb = new StringBuilder("0");
					dec = true;
				} else {
					sb.append(x.charAt(i));
					if (dec)
						f *= 10;
				}
			res += Long.parseLong(sb.toString()) / f;
			return res * (neg ? -1 : 1);
		}

		public boolean ready() throws IOException {
			return br.ready();
		}
	}

}