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.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.InputMismatchException;

public class F920{
	
	void solve()
	{
		int n = ni(), Q = ni();
		int[] a = ia(n);
		int[] fc = factorCount(1000000);
		int[] rc = recurseCount(fc);
		SegTree st = new SegTree(a, rc, fc);
		while(Q-->0)
		{
			int c = ni(), L = ni() - 1, R = ni() - 1;
			if(c == 1)
				st.update(0, 0, n - 1, L, R);
			else
				out.println(st.query(0, 0, n - 1, L, R));
		}
	}
	
	class SegTree {
		
		int size;
		int[] a, rc, fc;
		long[] st, rm;
		
		SegTree(int[] a, int[] rc, int[] fc)
		{
			this.a = a;
			this.rc = rc;
			this.fc = fc;
			size = 1;
			while(size < a.length) size <<= 1;
			size <<= 1;
			st = new long[size];
			rm = new long[size];
			build(0, 0, a.length - 1);
		}
		
		void build(int cur, int l, int r)
		{
			if(l == r)
			{
				st[cur] = a[l];
				rm[cur] = rc[a[l]];
				return;
			}
			int mid = l + r >> 1;
			build(2 * cur + 1, l, mid);
			build(2 * cur + 2, mid + 1, r);
			st[cur] = st[2 * cur + 1] + st[2 * cur + 2];
			rm[cur] = rm[2 * cur + 1] + rm[2 * cur + 2];
		}
		
		void update(int cur, int l, int r, int L, int R)
		{
			if(rm[cur] <= 0)
				return;
			if(l > R || r < L)
				return;
			if(L <= l && r <= R && l == r)
			{
				rm[cur]--;
				a[l] = fc[a[l]];
				st[cur] = a[l];
				return;
			}
			int mid = l + r >> 1;
			update(2 * cur + 1, l, mid, L, R);
			update(2 * cur + 2, mid + 1, r, L, R);
			st[cur] = st[2 * cur + 1] + st[2 * cur + 2];
			rm[cur] = rm[2 * cur + 1] + rm[2 * cur + 2];
		}
		
		long query(int cur, int l, int r, int L, int R)
		{
			if(l > R || r < L)
				return 0;
			if(L <= l && r <= R)
				return st[cur];
			int mid = l + r >> 1;
			long left = query(2 * cur + 1, l, mid, L, R);
			long right = query(2 * cur + 2, mid + 1, r, L, R);
			return left + right;
		}
	}
	
	int[] factorCount(int n)
	{
		int[] ans = new int[n+1];
		for(int i=1;i<=n;i++)
			for(int j=i;j<=n;j+=i)
				ans[j]++;
		return ans;
	}
	
	int[] recurseCount(int[] fc)
	{
		int[] ans = new int[fc.length];
		for(int i=3;i<fc.length;i++)
		{
			int cur = fc[i];
			int st = 0;
			while(cur > 2)
			{
				st++;
				cur = fc[cur];
			}
			ans[i] = st + 1;
		}
		return ans;
	}
	
	public static void main(String[] args){new F920().run();}
	
	private byte[] bufferArray = new byte[1024];
	private int bufLength = 0;
	private int bufCurrent = 0;
	InputStream inputStream;
	PrintWriter out;
	
	public void run()
	{
		inputStream = System.in;
		out = new PrintWriter(System.out);
		solve();
		out.flush();
	}
	
	int nextByte()
	{
		if(bufLength == -1)
			throw new InputMismatchException();
		if(bufCurrent >= bufLength)
		{
			bufCurrent = 0;
			try
			{bufLength = inputStream.read(bufferArray);}
			catch(IOException e)
			{ throw new InputMismatchException();}
			if(bufLength <= 0)
				return -1;
		}
		return bufferArray[bufCurrent++];
	}
	
	boolean isSpaceChar(int x)	{return (x < 33 || x > 126);}
	
	boolean isDigit(int x)	{return (x >= '0' && x <= '9');}
	
	int nextNonSpace()
	{
		int x;
		while((x=nextByte()) != -1 && isSpaceChar(x));
		return x;
	}
	
	int ni()
	{
		long ans = nl();
		if (ans >= Integer.MIN_VALUE && ans <= Integer.MAX_VALUE)
			return (int)ans;
		throw new InputMismatchException();
	}
	
	long nl()
	{
		long ans = 0;
		boolean neg = false;
		int x = nextNonSpace();
		if(x == '-') 
		{
			neg = true;
			x = nextByte();
		}
		while(!isSpaceChar(x))
		{
			if(isDigit(x))
			{
				ans = ans * 10 + x -'0';
				x = nextByte();
			}
			else
				throw new InputMismatchException();
		}
		return neg ? -ans : ans;
	}
	
	String ns()
	{
		StringBuilder sb = new StringBuilder();
		int x = nextNonSpace();
		while(!isSpaceChar(x))
		{
			sb.append((char)x);
			x = nextByte();
		}
		return sb.toString();
	}
	
	char nc()	{ return (char)nextNonSpace();}
	
	double nd()	{ return (double)Double.parseDouble(ns()); }
	
	char[] ca()	{ return ns().toCharArray();}
	
	char[][] ca(int n)
	{
		char[][] ans = new char[n][];
		for(int i=0;i<n;i++)
			ans[i] = ca();
		return ans;
	}
	
	int[] ia(int n)
	{
		int[] ans = new int[n];
		for(int i=0;i<n;i++)
			ans[i] = ni();
		return ans;
	}
	
	void db(Object... o) {System.out.println(Arrays.deepToString(o));}
	
}