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 org.omg.CORBA.MARSHAL;
    
    import java.util.*;
    import java.io.*;
    
    public class Main {
    
        public static void main(String[] args) throws IOException {
            Scanner sc = new Scanner(System.in);
            PrintWriter pw = new PrintWriter(System.out);
            int[]count = new int[(int)1e6+1];
            for (int i =1;i<=1e6;i++){
                for (int j = i;j<=1e6;j+=i)
                    count[j]++;
            }
            int n = sc.nextInt();
            int m = sc.nextInt();
            TreeSet<Integer>ts = new TreeSet<>();
            int[]a= sc.nextIntArr(n);
            for (int i =0;i<n;i++)ts.add(i);
            FenwickTree fn = new FenwickTree(n);
            for (int i =0;i<n;i++) {
                fn.point_update(i + 1, a[i]);
                ts.add(i);
            }
            while (m-->0){
                if (sc.nextInt()==1){
                    int l = sc.nextInt()-1;
                    int r = sc.nextInt();
                    ArrayList<Integer>done = new ArrayList<>();
                    for (int x:ts.subSet(l,r)){
                        if (a[x]==count[a[x]])
                            done.add(x);
                        else {
                            fn.point_update(x+1,-a[x]+count[a[x]]);
                            a[x]=count[a[x]];
                        }
                    }
                    for (int x:done)
                        ts.remove(x);
                }
                else {
                    pw.println(fn.rsq(sc.nextInt(),sc.nextInt()));
                }
            }
            pw.close();
    
        }
        static class FenwickTree { // one-based DS
    
            int n;
            long[] ft;
    
            FenwickTree(int size) { n = size; ft = new long[n+1]; }
    
            long rsq(int b) //O(log n)
            {
                long sum = 0;
                while(b > 0) { sum += ft[b]; b -= b & -b;}		//min?
                return sum;
            }
    
            long rsq(int a, int b) { return rsq(b) - rsq(a-1); }
    
            void point_update(int k, int val)	//O(log n), update = increment
            {
                while(k <= n) { ft[k] += val; k += k & -k; }		//min?
            }
        }
        static class Scanner {
            BufferedReader br;
            StringTokenizer st;
    
            public Scanner(InputStream s) {
                br = new BufferedReader(new InputStreamReader(s));
            }
    
            public String next() throws IOException {
                while (st == null || !st.hasMoreTokens())
                    st = new StringTokenizer(br.readLine());
                return st.nextToken();
            }
    
            public int nextInt() throws IOException {
                return Integer.parseInt(next());
            }
    
            public long nextLong() throws IOException {
                return Long.parseLong(next());
            }
    
            public double nextDouble() throws IOException {
                return Double.parseDouble(next());
            }
    
            public int[] nextIntArr(int n) throws IOException {
                int[] arr = new int[n];
                for (int i = 0; i < n; i++) {
                    arr[i] = Integer.parseInt(next());
                }
                return arr;
            }
    
        }
    
    }