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.InputStreamReader;
import java.io.PrintWriter;
import java.util.StringTokenizer;

public class P920F
{
	static int[] div = new int[1000001];
	public static void main(String[] args)
	{
		for (int i = 1; i <= 1000000; i++)
			for (int j = i; j < div.length; j += i)
				div[j]++;
		FastScanner scan = new FastScanner();
		PrintWriter pw = new PrintWriter(System.out);
		int n = scan.nextInt();
		int m = scan.nextInt();
		int[] arr = new int[n+1];
		for (int i = 1; i <= n; i++)
			arr[i] = scan.nextInt();
		SegTree seg = new SegTree(arr);
		for (int i = 0; i < m; i++)
		{
			int t = scan.nextInt();
			int a = scan.nextInt();
			int b = scan.nextInt();
			if (t == 1)
				seg.replace(a, b);
			else
				pw.println(seg.sum(a, b));
		}
		pw.flush();
	}
	static class SegTree
	{
		int[] arr;
		int[] left, right;
		long[] sum;
		boolean[] done;
		SegTree(int[] a)
		{
			int n = a.length-1;
			left = new int[4*n];
			right = new int[4*n];
			sum = new long[4*n];
			done = new boolean[4*n];
			arr = a;
			init(1, 1, n);
		}
		long sum(int a, int b)
		{
			return sum(1, a, b);
		}
		private long sum(int n, int a, int b)
		{
			if (right[n] < a || b < left[n])
				return 0;
			else if (a <= left[n] && right[n] <= b)
				return sum[n];
			long sumL = sum(2*n, a, b);
			long sumR = sum(2*n+1, a, b);
			update(n);
			return sumL+sumR;
		}
		void update(int n)
		{
			sum[n] = sum[2*n] + sum[2*n+1];
			done[n] = done[2*n] && done[2*n+1];
		}
		void replace(int a, int b)
		{
			replace(1, a, b);
		}
		private void replace(int n, int a, int b)
		{
			if (right[n] < a || b < left[n])
				return;
			else if (a <= left[n] && right[n] <= b)
			{
				if (done[n])
					return;
				if (left[n] == right[n])
				{
					int d = div[(int)sum[n]];
					if (d == sum[n])
						done[n] = true;
					else
						sum[n] = d;
					return;
				}
			}
			replace(2*n, a, b);
			replace(2*n+1, a, b);
			update(n);
		}
		void init(int n, int a, int b)
		{
			left[n] = a;
			right[n] = b;
			if (a == b)
			{
				sum[n] = arr[a];
				return;
			}
			int m = (a+b)/2;
			init(2*n, a, m);
			init(2*n+1, m+1, b);
			update(n);
		}
	}
	static class FastScanner
	{
		BufferedReader br;
		StringTokenizer st;

		public FastScanner()
		{
			try
			{
				br = new BufferedReader(new InputStreamReader(System.in));
				st = new StringTokenizer(br.readLine());
			} 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 String nextLine()
		{
			String line = "";
			try
			{
				line = br.readLine();
			} catch (Exception e)
			{
				e.printStackTrace();
			}
			return line;
		}
	}
}