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 CF920F {
	static final int A = 1000000;
	static int[] dd = new int[A + 1];
	static void init() {
		for (int a = 1; a <= A; a++)
			for (int b = a; b <= A; b += a)
				dd[b]++;
	}
	static int[] aa;
	static long[] tt;
	static boolean[] is2;
	static void pull(int k) {
		tt[k] = tt[k + k + 1] + tt[k + k + 2];
		if (is2[k + k + 1] && is2[k + k + 2])
			is2[k] = true;
	}
	static void build(int k, int l, int r) {
		if (r - l == 1) {
			tt[k] = aa[l];
			return;
		}
		int m = (l + r) / 2;
		build(k + k + 1, l, m);
		build(k + k + 2, m, r);
		pull(k);
	}
	static void update(int k, int l, int r, int ql, int qr) {
		if (qr <= l || r <= ql || is2[k])
			return;
		if (r - l == 1) {
			tt[k] = dd[(int) tt[k]];
			if (tt[k] <= 2)
				is2[k] = true;
			return;
		}
		int m = (l + r) / 2;
		update(k + k + 1, l, m, ql, qr);
		update(k + k + 2, m, r, ql, qr);
		pull(k);
	}
	static long query(int k, int l, int r, int ql, int qr) {
		if (qr <= l || r <= ql)
			return 0;
		if (ql <= l && r <= qr)
			return tt[k];
		int m = (l + r) / 2;
		long q1 = query(k + k + 1, l, m, ql, qr);
		long q2 = query(k + k + 2, m, r, ql, qr);
		return q1 + q2;
	}
	public static void main(String[] args) throws IOException {
		init();
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		PrintWriter pw = new PrintWriter(System.out);
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		st = new StringTokenizer(br.readLine());
		aa = new int[n];
		for (int i = 0; i < n; i++)
			aa[i] = Integer.parseInt(st.nextToken());
		tt = new long[n * 4];
		is2 = new boolean[n * 4];
		build(0, 0, n);
		while (m-- > 0) {
			st = new StringTokenizer(br.readLine());
			int t = Integer.parseInt(st.nextToken());
			int l = Integer.parseInt(st.nextToken()) - 1;
			int r = Integer.parseInt(st.nextToken());
			if (t == 1)
				update(0, 0, n, l, r);
			else
				pw.println(query(0, 0, n, l, r));
		}
		pw.close();
	}
}