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.*;

public class Main {
    public static void main(String[] args) throws IOException {
        InputReader in = new InputReader();
        PrintWriter out = new PrintWriter(System.out);
        Solver s = new Solver();
        int test = 1;
        for (int i = 1; i <= test; i++) {
            s.solve(i, in, out);
        }
        out.close();
    }
}

class Solver {

    private static final int MAX = (int) (1e6 + 7);
    private int[] p;
    private int[] c;

    void solve(int test_case, InputReader in, PrintWriter out) throws IOException {
        sieve();
        int n = in.nextInt();
        int q = in.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = in.nextInt();
        }
        segmentTree tree = new segmentTree(n, a);
//        System.out.println(Arrays.toString(a));
        TreeSet<Integer> set = new TreeSet<>();
        for (int i = 0; i < n; i++) {
            set.add(i);
        }
        while (q-- > 0) {
            int t = in.nextInt();
            int l = in.nextInt() - 1;
            int r = in.nextInt() - 1;
            if (t == 1) {
                TreeSet<Integer> st = (TreeSet<Integer>) set.tailSet(l);
                ArrayList<Integer> remove = new ArrayList<>();
                for (int x : st) {
                    if (x > r) break;
                    tree.Update(x, c[a[x]]);
                    int before = a[x];
                    a[x] = c[a[x]];
                    if (a[x] <= 2) {
//                        System.out.println(" ! " + before + " ! " + a[x]);
                        remove.add(x);
                    }
                }
                for (int x : remove) set.remove(x);
//                System.out.println(set);
            } else {
//                System.out.println(set);
//                System.out.println(Arrays.toString(a));
                out.println(tree.Query(l, r));
            }
        }
    }

    private void sieve() {
        p = new int[MAX];
        c = new int[MAX];
        for (int i = 2; i < MAX; i++) {
            if (p[i] == 0) {
                for (int j = i; j < MAX; j += i) p[j] = i;
            }
        }
        c[1] = 1;
        for (int i = 2; i < MAX; i++) {
            int x = i;
            int ans = 1;
            while (x > 1) {
                int j = p[x];
                int e = 0;
                while (x % j == 0) {
                    x /= j;
                    e++;
                }
                ans *= (e + 1);
            }
            c[i] = ans;
        }
    }


    static class segmentTree {

        long[] tree, a, lazy;
        int n;

        segmentTree(int n, int[] a) {
            int size = 1;
            while (size < 2 * a.length) size *= 2;
            tree = new long[size];
            lazy = new long[size];
            this.a = new long[n];
            for (int i = 0; i < n; i++) this.a[i] = a[i];
            this.n = n;
            build(0, 0, n - 1);
        }

        void build(int node, int start, int end) {
            if (start == end) {
                tree[node] = this.a[start];
            } else {
                int mid = (start + end) / 2;
                build(2 * node + 1, start, mid);
                build(2 * node + 2, mid + 1, end);
                tree[node] = (tree[2 * node + 1] + tree[2 * node + 2]);
            }
        }

        public long Query(int l, int r) {
            return query(0, 0, n - 1, l, r);
        }

        private long query(int node, int start, int end, int l, int r) {
            if (start > r || end < l) return 0;
            if (start >= l && end <= r) return tree[node];
            int mid = (start + end) / 2;
            long x = query(2 * node + 1, start, mid, l, r);
            long y = query(2 * node + 2, mid + 1, end, l, r);
            return x + y;
        }


        public void Update(int pos, int value) {
            update(0, 0, n - 1, pos, value);
        }

        private void update(int node, int start, int end, int pos, int value) {
            if (start == end) {
                tree[node] = value;
                this.a[start] = value;
            } else {
                int mid = (start + end) / 2;
                if (start <= pos && pos <= mid) update(2 * node + 1, start, mid, pos, value);
                else update(2 * node + 2, mid + 1, end, pos, value);
                tree[node] = (tree[2 * node + 1] + tree[2 * node + 2]);
            }
        }

        public void UpdateRange(int l, int r, int val) {
            updateRange(0, 0, n - 1, l, r, val);
        }

        private void updateRange(int node, int start, int end, int l, int r, int val) {
            if (lazy[node] != 0) {
                tree[node] += (end - start + 1) * lazy[node];
                if (start != end) {
                    lazy[2 * node + 1] += lazy[node];
                    lazy[2 * node + 2] += lazy[node];
                }
                lazy[node] = 0;
            }
            if (start > r || end < l) return;
            if (l <= start && end <= r) {
                tree[node] += (end - start + 1) * val;
                if (start != end) {
                    lazy[2 * node + 1] += val;
                    lazy[2 * node + 2] += val;
                }
                return;
            }
            int mid = (start + end) / 2;
            updateRange(2 * node + 1, start, mid, l, r, val);
            updateRange(2 * node + 2, mid + 1, end, l, r, val);
            tree[node] = tree[2 * node + 1] + tree[2 * node + 2];
        }

        public long QueryRange(int l, int r) {
            return queryRange(0, 0, n - 1, l, r);
        }

        private long queryRange(int node, int start, int end, int l, int r) {
            if (start > r || end < l) return 0;
            if (lazy[node] != 0) {
                tree[node] += (end - start + 1) * lazy[node];
                if (start != end) {
                    lazy[node * 2 + 1] += lazy[node];
                    lazy[node * 2 + 2] += lazy[node];
                }
                lazy[node] = 0;                 // Reset it
            }
            if (start >= l && end <= r) return tree[node];
            int mid = (start + end) / 2;
            long p1 = queryRange(node * 2 + 1, start, mid, l, r);         // Query left child
            long p2 = queryRange(node * 2 + 2, mid + 1, end, l, r); // Query right child
            return (p1 + p2);
        }
    }
}


class InputReader {
    final private int BUFFER_SIZE = 1 << 16;
    private DataInputStream din;
    private byte[] buffer;
    private int bufferPointer, bytesRead;

    public InputReader() {
        din = new DataInputStream(System.in);
        buffer = new byte[BUFFER_SIZE];
        bufferPointer = bytesRead = 0;
    }

    public InputReader(String file_name) throws IOException {
        din = new DataInputStream(new FileInputStream(file_name));
        buffer = new byte[BUFFER_SIZE];
        bufferPointer = bytesRead = 0;
    }

    public String nextLine() throws IOException {
        byte[] buf = new byte[64]; // line length
        int cnt = 0, c;
        while ((c = read()) != -1) {
            if (c == '\n')
                break;
            buf[cnt++] = (byte) c;
        }
        return new String(buf, 0, cnt);
    }

    public int nextInt() throws IOException {
        int ret = 0;
        byte c = read();
        while (c <= ' ')
            c = read();
        boolean neg = (c == '-');
        if (neg)
            c = read();
        do {
            ret = ret * 10 + c - '0';
        } while ((c = read()) >= '0' && c <= '9');

        if (neg)
            return -ret;
        return ret;
    }

    public long nextLong() throws IOException {
        long ret = 0;
        byte c = read();
        while (c <= ' ')
            c = read();
        boolean neg = (c == '-');
        if (neg)
            c = read();
        do {
            ret = ret * 10 + c - '0';
        }
        while ((c = read()) >= '0' && c <= '9');
        if (neg)
            return -ret;
        return ret;
    }

    public double nextDouble() throws IOException {
        double ret = 0, div = 1;
        byte c = read();
        while (c <= ' ')
            c = read();
        boolean neg = (c == '-');
        if (neg)
            c = read();

        do {
            ret = ret * 10 + c - '0';
        }
        while ((c = read()) >= '0' && c <= '9');

        if (c == '.') {
            while ((c = read()) >= '0' && c <= '9') {
                ret += (c - '0') / (div *= 10);
            }
        }

        if (neg)
            return -ret;
        return ret;
    }

    private void fillBuffer() throws IOException {
        bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
        if (bytesRead == -1)
            buffer[0] = -1;
    }

    private byte read() throws IOException {
        if (bufferPointer == bytesRead)
            fillBuffer();
        return buffer[bufferPointer++];
    }

    public void close() throws IOException {
        if (din == null)
            return;
        din.close();
    }

    public String next() throws IOException {
        byte[] buf = new byte[64]; // line length
        int cnt = 0, c;
        while ((c = read()) != -1) {
            if (c == '\n' || c == ' ')
                break;
            buf[cnt++] = (byte) c;
        }
        return new String(buf, 0, cnt);
    }
}