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.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.StringTokenizer;
import java.util.HashMap;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        SUMandREPLACE solver = new SUMandREPLACE();
        solver.solve(1, in, out);
        out.close();
    }

    static class SUMandREPLACE {
        final int MAX = (int) 1e6 + 5;
        int n;
        int m;
        int[] arr;
        int[] divisors = new int[MAX];
        int[] spf = new int[MAX];
        Node[] tree;

        void init() {
            spf[1] = 1;
            for (int i = 2; i < MAX; i++) spf[i] = (i % 2 == 0 ? 2 : i);
            for (int i = 3; i * i < MAX; i++) {
                if (spf[i] == i) {
                    for (int j = i * i; j < MAX; j += i) {
                        if (spf[j] == j) spf[j] = i;
                    }
                }
            }
            Arrays.fill(divisors, 1);
            Occurrences<Integer> factors;
            for (int i = 2; i < MAX; i++) {
                factors = new Occurrences<>();
                int j = i;
                while (j != 1) {
                    factors.increment(spf[j]);
                    j /= spf[j];
                }
                for (int factor : factors.keySet()) {
                    divisors[i] *= factors.get(factor) + 1;
                }
            }
        }

        public void solve(int testNumber, InputReader in, PrintWriter out) {
            init();
            n = in.nextInt();
            m = in.nextInt();
            arr = in.nextIntArray(1, n);
            tree = new Node[4 * n + 5];
            build(1, 1, n);
            for (int i = 1; i <= m; i++) {
                int arg1 = in.nextInt(), arg2 = in.nextInt(), arg3 = in.nextInt();
                if (arg1 == 1) {
                    update(1, 1, n, arg2, arg3);
                } else {
                    out.println(query(1, 1, n, arg2, arg3));
                }
            }
        }

        int l(int n) {
            return (n << 1);
        }

        int r(int n) {
            return (1 + (n << 1));
        }

        int m(int l, int r) {
            return (l + r) >> 1;
        }

        void build(int n, int l, int r) {
            if (l == r) tree[n] = new Node(arr[l]);
            else {
                int m = m(l, r);
                build(l(n), l, m);
                build(r(n), m + 1, r);
                tree[n] = tree[l(n)].combine(tree[r(n)]);
            }
        }

        void update(int n, int l, int r, int a, int b) {
            if (l > b || r < a) return;
            if (tree[n].twos + tree[n].ones == (r - l + 1)) return;
            if (l == r) tree[n] = new Node(arr[l] = divisors[arr[l]]);
            else {
                int m = m(l, r);
                update(l(n), l, m, a, b);
                update(r(n), m + 1, r, a, b);
                tree[n] = tree[l(n)].combine(tree[r(n)]);
            }
        }

        long query(int n, int l, int r, int a, int b) {
            if (l > b || r < a) return 0;
            if (a <= l && r <= b) return tree[n].sum;
            return (query(l(n), l, m(l, r), a, b) + query(r(n), m(l, r) + 1, r, a, b));
        }

        class Node {
            int twos;
            int ones;
            long sum;

            Node(long sum) {
                this.sum = sum;
                if (sum == 2) twos = 1;
                if (sum == 1) ones = 1;
            }

            Node(int twos, int ones, long sum) {
                this.twos = twos;
                this.ones = ones;
                this.sum = sum;
            }

            Node combine(Node n) {
                return (new Node(ones + n.ones, twos + n.twos, sum + n.sum));
            }

        }

    }

    static class Occurrences<E> extends HashMap<E, Integer> {
        public void increment(E key) {
            Integer occ = get(key);
            if (occ == null) occ = 0;
            put(key, occ + 1);
        }

    }

    static class InputReader {
        private StringTokenizer tokenizer;
        private BufferedReader reader;

        public InputReader(InputStream inputStream) {
            reader = new BufferedReader(new InputStreamReader(inputStream));
        }

        private void fillTokenizer() {
            if (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (Exception e) {
                    throw new RuntimeException(e);
                }
            }
        }

        public String next() {
            fillTokenizer();
            return tokenizer.nextToken();
        }

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

        public int[] nextIntArray(int offset, int length) {
            int[] arr = new int[offset + length];
            for (int i = offset; i < offset + length; i++) {
                arr[i] = nextInt();
            }
            return arr;
        }

    }
}