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.math.BigInteger;
import java.util.*;
import java.util.Map.Entry;

	
public class Main
	{
		private InputStream stream;
		private byte[] buf = new byte[1024];
		private int curChar;
		private int numChars;
		private SpaceCharFilter filter;
		private PrintWriter pw;
		private long mod = 1000000000 + 7;
		
		private StringBuilder ans_sb;
		private int block;
		private double ans = 0;
		int[] s;
		private void soln()
		{
			int n = nextInt();
			int m = nextInt();
			int[] arr = nextIntArray(n);
		//	TreeSet<Integer> set = new TreeSet<>();
			Segment tree = new Segment(n,arr);
			s = new int[1000001];
			for(int i=1;i<=1000000;i++) {
				for(int j=i;j<=1000000;j+=i)
					s[j]++;
			}
		//	debug(s);
			for(int i=0;i<m;i++) {
				int t = nextInt();
				int l = nextInt() - 1;
				int r = nextInt() - 1;
				if(t==1) {					
					tree.update(l, r, 1);			
				}else {
					pw.println(tree.query(l, r));
				}
			}
		}
		public class Segment
		{
			private long[] tree;
			private int[] base;
			private int[] lazy;
			private int size;
			private int n;

			private class Node
			{
				private int l;
				private int r;
				private long ans;
			}

			public Segment(int n, int[] arr)
			{
				this.base=arr;
				int x = (int) (Math.ceil(Math.log(n) / Math.log(2)));
				size = 2 * (int) Math.pow(2, x) - 1;
				tree = new long[size];
				lazy = new int[size];
				this.n = n;
				//this.set = set1;
				build(0, 0, n - 1);
			}

			public void build(int id, int l, int r)
			{
				if (l == r)
				{				
					tree[id] = base[l];
					if(tree[id] == 1 || tree[id] == 2)
						lazy[id] = 1;
					return;
				}
				int mid =( (l + r) >>1);
				build(2 * id + 1, l, mid);
				build(2 * id + 2, mid + 1, r);
				tree[id] = tree[(id<<1)|1]+ tree[(id<<1)+2];
				lazy[id] = lazy[(id<<1)|1]+ lazy[(id<<1)+2];
			}
			public long query(int l, int r)
			{
				return queryUtil(l, r, 0, 0, n - 1);
			}

			private long queryUtil(int x, int y, int id, int l, int r)
			{
				if (l > y || x > r)
					return 0;
				if (x <= l && r <= y)
				{
					return tree[id];
				}
				int mid = ( (l + r) >>1);
			//	shift(id);
				return queryUtil(x, y, (id<<1)|1, l, mid) + queryUtil(x, y, (id<<1)+2, mid + 1, r);
			}
			
			public void update(int x, int y, int c) {
				update1(x, y, c, 0, 0, n-1);
			}
			
			private void update1(int x, int y, int colour, int id, int l, int r)
			{
				//System.out.println(l+" "+r+" "+x);
				if (x > r || y < l)
					return;
				if (x <= l && r <= y)
				{
					if(lazy[id] == (r-l+1))
						return;
					else if(l==r) {
						tree[id] = s[(int) tree[id]];
						if(tree[id] == 1 || tree[id] == 2)
							lazy[id] = 1;
						return;
					}
				}
				int mid =( (l + r) >>1);
			//	shift(id);
				if(y<=mid)
					update1(x, y, colour, (id<<1) | 1, l, mid);
				else if(x>mid)
					update1(x, y, colour, (id<<1) + 2, mid + 1, r);
				else {
					update1(x, y, colour, (id<<1)| 1, l, mid);
					update1(x, y, colour, (id<<1) + 2, mid + 1, r);
				}
				tree[id] = tree[(id<<1)|1] + tree[(id<<1)+2];
				lazy[id] = lazy[(id<<1)|1] + lazy[(id<<1)+2];
			}
		}
		private class Pair implements Comparable<Pair>{
			long s,h,ans;
			public Pair(long a,long b,long c) {
				s = a;
				h = b;
				ans = c;
			}
			@Override
			public int compareTo(Pair arg0)
			{
				long mul1 = this.s * arg0.h;
				long mul2 = this.h * arg0.s;
			//	if(mul1 != mul2)
				if(mul1>mul2)
					return -1;
				else if(mul2 > mul1)
					return 1;
				return 0;
				
			//	return 0;
			}
		}
		private String solveEqn(long a, long b) {
	        long x = 0, y = 1, lastx = 1, lasty = 0, temp;
	        while (b != 0){
	        	long q = a / b;
	        	long r = a % b;
	            a = b;
	            b = r;
	            temp = x;
	            x = lastx - q * x;
	            lastx = temp;
	            temp = y;
	            y = lasty - q * y;
	            lasty = temp;
	        }
	        return lastx+" "+lasty;
		}
		private void debug(Object... o) {
			System.out.println(Arrays.deepToString(o));
		}
		
		private long pow(long a, long b, long c)
		{
			if (b == 0)
				return 1;
			long p = pow(a, b / 2, c);
			p = (p * p) % c;
			return (b % 2 == 0) ? p : (a * p) % c;
		}
	
		private long gcd(long n, long l)
		{
			if (l == 0)
				return n;
			return gcd(l, n % l);
		}
		public static void main(String[] args) throws Exception
		{
			new Thread(null, new Runnable()
			{
				@Override
				public void run()
				{
					new Main().solve();
				}
			}, "1", 1 << 25).start();
		//	new Main().solve();
		}
		public StringBuilder solve(){
			InputReader(System.in);
			/*try { 
				InputReader(new FileInputStream("C:\\Users\\hardik\\Desktop\\in.txt"));
			} catch(FileNotFoundException e) {}
			*/
			pw = new PrintWriter(System.out);
			//ans_sb = new StringBuilder();
			soln();
			
			pw.close();
			//System.out.println(ans_sb);
			return ans_sb;
		}
		public void InputReader(InputStream stream1)
		{
			stream = stream1;
		}
	
		private boolean isWhitespace(int c)
		{
			return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
		}
	
		private boolean isEndOfLine(int c)
		{
			return c == '\n' || c == '\r' || c == -1;
		}
	
		private int read()
		{
			if (numChars == -1)
				throw new InputMismatchException();
			if (curChar >= numChars)
			{
				curChar = 0;
				try
				{
					numChars = stream.read(buf);
				} catch (IOException e)
				{
					throw new InputMismatchException();
				}
				if (numChars <= 0)
					return -1;
			}
			return buf[curChar++];
		}
	
		private int nextInt()
		{
			int c = read();
			while (isSpaceChar(c))
				c = read();
			int sgn = 1;
			if (c == '-')
			{
				sgn = -1;
				c = read();
			}
			int res = 0;
			do
			{
				if (c < '0' || c > '9')
					throw new InputMismatchException();
				res *= 10;
				res += c - '0';
				c = read();
			} while (!isSpaceChar(c));
			return res * sgn;
		}
	
		private long nextLong()
		{
			int c = read();
			while (isSpaceChar(c))
				c = read();
			int sgn = 1;
			if (c == '-')
			{
				sgn = -1;
				c = read();
			}
			long res = 0;
			do
			{
				if (c < '0' || c > '9')
					throw new InputMismatchException();
				res *= 10;
				res += c - '0';
				c = read();
			} while (!isSpaceChar(c));
			return res * sgn;
		}
	
		private String nextToken()
		{
			int c = read();
			while (isSpaceChar(c))
				c = read();
			StringBuilder res = new StringBuilder();
			do
			{
				res.appendCodePoint(c);
				c = read();
			} while (!isSpaceChar(c));
			return res.toString();
		}
	
		private String nextLine()
		{
			int c = read();
			while (isSpaceChar(c))
				c = read();
			StringBuilder res = new StringBuilder();
			do
			{
				res.appendCodePoint(c);
				c = read();
			} while (!isEndOfLine(c));
			return res.toString();
		}
	
		private int[] nextIntArray(int n)
		{
			int[] arr = new int[n];
			for (int i = 0; i < n; i++)
			{
				arr[i] = nextInt();
			}
			return arr;
		}
	
		private long[] nextLongArray(int n)
		{
			long[] arr = new long[n];
			for (int i = 0; i < n; i++)
			{
				arr[i] = nextLong();
			}
			return arr;
		}
	
		private void pArray(int[] arr)
		{
			for (int i = 0; i < arr.length; i++)
			{
				System.out.print(arr[i] + " ");
			}
			System.out.println();
			return;
		}
	
		private void pArray(long[] arr)
		{
			for (int i = 0; i < arr.length; i++)
			{
				System.out.print(arr[i] + " ");
			}
			System.out.println();
			return;
		}
	
		private boolean isSpaceChar(int c)
		{
			if (filter != null)
				return filter.isSpaceChar(c);
			return isWhitespace(c);
		}
	
		private char nextChar()
		{
			int c = read();
			while (isSpaceChar(c))
				c = read();
			char c1 = (char) c;
			while (!isSpaceChar(c))
				c = read();
			return c1;
		}
	
		private interface SpaceCharFilter
		{
			public boolean isSpaceChar(int ch);
		}
	}