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:
// package CodeForces;

import java.io.BufferedOutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.InputMismatchException;

public class EducationalRound37F {

	public static final int max = (int)1e6 + 5;
	public static int[] divisors;
	
	public static class Node {
		long[] values;
		int ones;
		int start;
		int end;
		
		public Node(int number, int start, int end) {
			values = new long[10];
			int ptr = 0;
			while(ptr < 10) {
				values[ptr++] = number;
				number = divisors[number];
			}
			if(number == 1) {
				this.ones = 1;
			}
			this.start = start;
			this.end = end;
		}
		
		public Node(Node A, Node B) {
			this.values = new long[10];
			for(int i = 0; i < 10; i++) {
				this.values[i] = A.values[i] + B.values[i];
			}
			this.ones = A.ones + B.ones;
			this.start = A.start;
			this.end = B.end;
		}
		
		public void Update() {
			int non_ones = end - start + 1 - this.ones;
			for(int i = 0; i < 9; i++) {
				values[i] = values[i + 1];
			}
			values[9] = (long)non_ones * 2L + (long)this.ones;
		}
		
		public long Value() {
			int non_ones = end - start + 1 - this.ones;
			return (long)non_ones * 2L + (long)this.ones;
		}
	}
	
	public static Node[] st;
	public static int[] lazy;
	
	public static void Build(int start, int end, int index, int[] arr) {
		if(start == end) {
			st[index] = new Node(arr[start], start, end);
			return;
		}
		int mid = (start + end)>>1;
		int left = index<<1, right = index<<1|1;
		Build(start, mid, left, arr);
		Build(mid + 1, end, right, arr);
		st[index] = new Node(st[left], st[right]);
	}
	
	public static void Update(int start, int end, int index, int l, int r) {
		if(lazy[index] != 0) {
			int times = lazy[index];
			if(times > 10) {
				times = 10;
			}
			if(start != end) {
				lazy[index<<1] += times;
				lazy[index<<1|1] += times;
			}
			long value = st[index].Value();
			while(times > 0 && st[index].values[0] != value) {
				times--;
				st[index].Update();
			}
			lazy[index] = 0;
		}
		if(l > end || start > r) {
			return;
		}
		if(l <= start && end <= r) {
			st[index].Update();
			if(start != end) {
				lazy[index<<1]++;
				lazy[index<<1|1]++;
			}
			return;
		}
		int mid = (start + end)>>1;
		Update(start, mid, index<<1, l, r);
		Update(mid + 1, end, index<<1|1, l, r);
		st[index] = new Node(st[index<<1], st[index<<1|1]);
	}
	
	public static long Query(int start, int end, int index, int l, int r) {
		if(lazy[index] != 0) {
			int times = lazy[index];
			if(times > 10) {
				times = 10;
			}
			if(start != end) {
				lazy[index<<1] += times;
				lazy[index<<1|1] += times;
			}
			long value = st[index].Value();
			while(times > 0 && st[index].values[0] != value) {
				times--;
				st[index].Update();
			}
			lazy[index] = 0;
		}
		if(l > end || start > r) {
			return 0;
		}
		if(l <= start && end <= r) {
			return st[index].values[0];
		}
		int mid = (start + end)>>1;
		return Query(start, mid, index<<1, l, r) + Query(mid + 1, end, index<<1|1, l, r);
	}
	
	public static void solve() {
		divisors = new int[max];
		for(int i = 1; i < max; i++) {
			for(int j = i; j < max; j += i) {
				divisors[j] ++;
			}
		}
//		out.println(divisors[10]);
		int n = s.nextInt();
		int m = s.nextInt();
		int[] arr = s.nextIntArray(n);
		st = new Node[4 * n + 1];
		lazy = new int[4 * n + 1];
		Build(0, n - 1, 1, arr);
		while(m-- > 0) {
			int type = s.nextInt();
			if(type == 2) {
				int l = s.nextInt() - 1;
				int r = s.nextInt() - 1;
				long ans = Query(0, n - 1, 1, l, r);
				out.println(ans);
			}else {
				int l = s.nextInt() - 1;
				int r = s.nextInt() - 1;
				Update(0, n - 1, 1, l, r);
			}
		}
	}

	public static void main(String[] args) {
		new Thread(null, null, "Thread", 1 << 27) {
			public void run() {
				try {
					out = new PrintWriter(new BufferedOutputStream(System.out));
					s = new FastReader(System.in);
					solve();
					out.close();
				} catch (Exception e) {
					e.printStackTrace();
					System.exit(1);
				}
			}
		}.start();
	}

	public static PrintWriter out;
	public static FastReader s;

	public static class FastReader {

		private InputStream stream;
		private byte[] buf = new byte[4096];
		private int curChar, snumChars;

		public FastReader(InputStream stream) {
			this.stream = stream;
		}

		public int read() {
			if (snumChars == -1) {
				throw new InputMismatchException();
			}
			if (curChar >= snumChars) {
				curChar = 0;
				try {
					snumChars = stream.read(buf);
				} catch (IOException E) {
					throw new InputMismatchException();
				}
			}
			if (snumChars <= 0) {
				return -1;
			}
			return buf[curChar++];
		}

		public int nextInt() {
			int c = read();
			while (isSpaceChar(c)) {
				c = read();
			}
			int sgn = 1;
			if (c == '-') {
				sgn = -1;
				c = read();
			}
			int number = 0;
			do {
				number *= 10;
				number += c - '0';
				c = read();
			} while (!isSpaceChar(c));
			return number * sgn;
		}

		public long nextLong() {
			int c = read();
			while (isSpaceChar(c)) {
				c = read();
			}
			long sgn = 1;
			if (c == '-') {
				sgn = -1;
				c = read();
			}
			long number = 0;
			do {
				number *= 10L;
				number += (long) (c - '0');
				c = read();
			} while (!isSpaceChar(c));
			return number * sgn;
		}

		public int[] nextIntArray(int n) {
			int[] arr = new int[n];
			for (int i = 0; i < n; i++) {
				arr[i] = this.nextInt();
			}
			return arr;
		}

		public long[] nextLongArray(int n) {
			long[] arr = new long[n];
			for (int i = 0; i < n; i++) {
				arr[i] = this.nextLong();
			}
			return arr;
		}

		public String next() {
			int c = read();
			while (isSpaceChar(c)) {
				c = read();
			}
			StringBuilder res = new StringBuilder();
			do {
				res.appendCodePoint(c);
				c = read();
			} while (!isSpaceChar(c));
			return res.toString();
		}

		public 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();
		}

		public boolean isSpaceChar(int c) {
			return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
		}

		public boolean isEndofLine(int c) {
			return c == '\n' || c == '\r' || c == -1;
		}

	}

	
}