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.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;
import java.util.TreeSet;

public class F {
	public static void main(String[] args) throws IOException {
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();
		int q = sc.nextInt();
		int[] arr = new int[n];
		for (int i = 0; i < n; i++)
			arr[i] = sc.nextInt();
		int[] divs = new int[1000001];
		Arrays.fill(divs, 1);
		for (int i = 2; i < divs.length; i++)
			if (divs[i] == 1) {
				divs[i] = 2;
				for (int j = i << 1; j < divs.length; j += i) {
					int cnt = 0;
					int jj = j;
					while (jj % i == 0) {
						cnt++;
						jj /= i;
					}
					divs[j] *= (cnt + 1);
				}
			}
		n++;
		tree = new long[n + 1];
		for (int i = 0; i < arr.length; i++)
			update(i + 1, arr[i]);

		TreeSet<Integer> free = new TreeSet<>();
		for (int i = 1; i <= n - 1; i++) {
			if (arr[i - 1] > 2)
				free.add(i);
		}
		PrintWriter pw = new PrintWriter(System.out);
		for (int i = 0; i < q; i++) {
			int type = sc.nextInt();
			int x = sc.nextInt();
			int y = sc.nextInt();
			if (type == 1) {
				if (arr[x - 1] > 2) {
					int now = arr[x - 1];
					update(x, divs[now] - now);
					arr[x - 1] = divs[now];
				}
				while (true) {
					Integer xx = free.higher(x);
					if (xx == null || (int)xx > y)
						break;
					x = xx;
					int now = arr[x-1];
					update(x, divs[now] - now);
					arr[x - 1] = divs[now];
					if(arr[x - 1] < 3)
						free.remove(x);
				}
			}
			else {
				pw.println(query(y) - query(x - 1));
			}
		}
		pw.flush();
	}

	static long[] tree;
	static int n;

	static long query(int idx) {
		long ret = 0;
		while (idx > 0) {
			ret += tree[idx];
			idx -= (idx & -idx);
		}
		return ret;
	}

	static void update(int idx, int val) {
		while (idx <= n) {
			tree[idx] += val;
			idx += (idx & -idx);
		}
	}

	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 double nextDouble() throws IOException {
			return Double.parseDouble(next());
		}

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