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.util.*;
import java.io.IOException;
import java.io.InputStream;
import java.util.StringTokenizer;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
 
public class Main {
    static int maxn = (int) (3e5 + 5);
    static int maxm = (int) (1e6 + 5);
    static int[] a = new int[maxn];
    static int[] d = new int[maxm];
    static int[] num = new int[maxm];
    static int[] p = new int[maxm];
    static int tot;
    static boolean[] np = new boolean[maxm];
    static void getD() {
    	np[0] = np[1] = true;
    	d[1] = 1;
    	tot = 0;
    	for(int i = 2; i < maxm; ++i) {
    		if(np[i] == false) {
    			p[tot++] = i;
    			d[i] = 2;
    			num[i] = 1;
    		}
    		for(int j = 0; j < tot; ++j) {
    			int x = p[j]*i;
    			if(x >= maxm) break;
    			np[x] = true;
    			if(i%p[j] == 0) {
    				d[x] = d[i]/(num[i] + 1)*(num[i] + 2);
    				num[x] = num[i] + 1;
    				break;
    			} else {
    				d[x] = 2*d[i];
    				num[x] = 1;
    			}
    		}
    	}
    }
    public static class SegTree {
    	int lf, rt;
    	int mx;
    	long sum;
    }
    static SegTree[] st = new SegTree[maxn<<2];
    static void PushUp(int x) {
    	st[x].mx = Math.max(st[x << 1].mx, st[x << 1 | 1].mx);
    	st[x].sum = st[x << 1].sum + st[x << 1 | 1].sum;
    }
    static void Build(int x, int lf, int rt) {
    	st[x] = new SegTree();
    	SegTree now = st[x];
    	now.lf = lf;
    	now.rt = rt;
    	if(lf == rt) {
    		now.mx = a[lf];
    		now.sum = a[lf];
    		return ;
    	}
    	int mid = (lf + rt) >> 1;
    	Build(x << 1, lf, mid);
    	Build(x << 1 | 1, mid + 1, rt);
    	PushUp(x);
    }
    static void Update(int x, int lf, int rt) {
    	SegTree now = st[x];
    	if(now.mx <= 2) return ;
    	if(now.lf == now.rt) {
    		now.mx = d[now.mx];
    		now.sum = now.mx;
    		return ;
    	}
    	int mid = (now.lf + now.rt) >> 1;
    	if(lf <= mid) Update(x << 1, lf, rt);
    	if(rt > mid) Update(x << 1 | 1, lf ,rt);
    	PushUp(x);
    }
    static long Query(int x, int lf, int rt) {
    	SegTree now = st[x];
    	if(lf <= now.lf && rt >= now.rt) return now.sum;
    	long ret = 0;
    	int mid = (now.lf + now.rt) >> 1;
    	if(lf <= mid) ret += Query(x << 1, lf, rt);
    	if(rt > mid) ret += Query(x << 1 | 1, lf ,rt);
    	return ret;
    }
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(System.out);
        getD();
        int n = in.nextInt();
        int m = in.nextInt();
        for(int i = 1; i <= n; ++i) {
        	a[i] = in.nextInt();
        }
        Build(1, 1, n);
        for(int i = 1; i <= m; ++i) {
        	int t = in.nextInt();
        	int l = in.nextInt();
        	int r = in.nextInt();
        	if(t == 1) {
        		Update(1, l, r);
        	} else {
        		out.println(Query(1, l, r));
        	}
        }
        out.flush();
        // Scanner in = new Scanner(System.in);
        // in.close();
    }
    static class InputReader {
        public BufferedReader reader;
        public StringTokenizer tokenizer;
        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }
        public String next() {
            while(tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }
        public int nextInt() {
            return Integer.parseInt(next());
        }
        public long nextLong() {
            return Long.parseLong(next());
        }
    }
}