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.util.Random;
import java.util.StringTokenizer;
import java.util.TreeSet;

public  class G {

    public static void main(String[] args) {
        FastReader scan = new FastReader();
        PrintWriter out = new PrintWriter(System.out);
        Task solver = new Task();
        int t = 1;
        for(int tt = 1; tt <= t; tt++) solver.solve(tt, scan, out);
        out.close();
    }

    static class Task {
        static int n, m, max = (int) 1e6;
        static long[] bit;
        static int[] a, numDivisor = new int[max+1];
        static TreeSet<Integer> canUpdate = new TreeSet<>();

        public void solve(int testNumber, FastReader scan, PrintWriter out) {
            n = scan.nextInt();
            m = scan.nextInt();
            bit = new long[n + 1];
            a = new int[n];
            for(int i = 1; i <= max; i++) {
                for(int j = i; j <= max; j += i) numDivisor[j]++;
            }
            for(int i = 0; i < n; i++) {
                a[i] = scan.nextInt();
                if(a[i] > 2) canUpdate.add(i);
                update(i, a[i]);
            }
            for(int i = 0; i < m; i++) {
                int q = scan.nextInt();
                int l = scan.nextInt() - 1, r = scan.nextInt() - 1;
                if(q == 2) {
                    out.println(sum(l - 1, r));
                }
                else {
                    Integer at = canUpdate.ceiling(l);
                    while(at != null && at <= r) {
                        update(at, numDivisor[a[at]] - a[at]);
                        a[at] = numDivisor[a[at]];
                        if(a[at] <= 2) canUpdate.remove(at);
                        at = canUpdate.higher(at);
                    }
                }
            }
        }

        static void update(int index, int val) {
            index++;
            while(index <= n) {
                bit[index] += val;
                index += index & (-index);
            }
        }

        static long sum(int index) {
            long ret = 0;
            index++;
            while(index > 0) {
                ret += bit[index];
                index -= index & (-index);
            }
            return ret;
        }

        static long sum(int l, int r) {
            return sum(r) - sum(l);
        }
    }

    static void shuffle(int[] a) {
        Random get = new Random();
        for (int i = 0; i < a.length; i++) {
            int r = get.nextInt(a.length);
            int temp = a[i];
            a[i] = a[r];
            a[r] = temp;
        }
    }

    static void shuffle(long[] a) {
        Random get = new Random();
        for (int i = 0; i < a.length; i++) {
            int r = get.nextInt(a.length);
            long temp = a[i];
            a[i] = a[r];
            a[r] = temp;
        }
    }

    static class FastReader {
        BufferedReader br;
        StringTokenizer st;

        public FastReader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        public FastReader(String s) throws FileNotFoundException {
            br = new BufferedReader(new FileReader(new File(s)));
        }

        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }

        String nextLine() {
            String str = "";
            try {
                str = br.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return str;
        }
    }

}