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.io.FilterInputStream;
import java.io.BufferedInputStream;
import java.io.InputStream;

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

    static class BK1 {
        int[] D;
        int[] lazy;
        int[] array;
        long[][] tree;

        private void pre() {
            D = new int[1000007];
            D[1] = 1;
            for (int i = 2; i < 1000007; i++) {
                D[i]++;
                for (int j = i; j < 1000007; j += i) D[j]++;
            }
        }

        private void updateLazy(int node, long val, int start, int end) {
            if (val != 0) {
                for (int i = 0; i <= 7; i++) {
                    if (i + val > 7) tree[node][i] = tree[node][7];
                    else tree[node][i] = tree[node][(int) (i + val)];
                }
                if (start != end) {
                    lazy[node << 1] += val;
                    lazy[(node << 1) + 1] += val;
                }
                lazy[node] = 0;
            }
        }

        private void update(int node, int start, int end, int l, int r) {
            updateLazy(node, lazy[node], start, end);
            if (tree[node][0] == (end - start + 1))
                return;
            if (l <= start && end <= r) {
                updateLazy(node, 1, start, end);
                return;
            }
            if (l > end || r < start) return;
            int mid = (start + end) >> 1;
            update(node << 1, start, mid, l, r);
            update((node << 1) + 1, mid + 1, end, l, r);
            for (int i = 0; i <= 7; i++) tree[node][i] = (tree[node << 1][i] + tree[(node << 1) + 1][i]);
        }

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

        private void build(int node, int start, int end) {
            if (start == end) {
                tree[node][0] = array[start];
                for (int i = 1; i <= 7; i++) tree[node][i] = D[(int) tree[node][i - 1]];
            } else {
                int mid = (start + end) >> 1;
                build(node << 1, start, mid);
                build((node << 1) + 1, mid + 1, end);
                for (int i = 0; i <= 7; i++) tree[node][i] = (tree[node << 1][i] + tree[(node << 1) + 1][i]);
            }
        }

        public void solve(int testNumber, ScanReader in, PrintWriter out) {
            int n = in.scanInt();
            int m = in.scanInt();
            array = new int[n + 1];
            tree = new long[4 * (n + 1)][8];
            lazy = new int[4 * (n + 1)];
            pre();
            for (int i = 1; i <= n; i++) array[i] = in.scanInt();
            build(1, 1, n);
            int state, l, r;
            while (m-- > 0) {
                state = in.scanInt();
                l = in.scanInt();
                r = in.scanInt();
                if (state == 1) update(1, 1, n, l, r);
                else out.println(query(1, 1, n, l, r));

            }
        }

    }

    static class ScanReader {
        private byte[] buf = new byte[4 * 1024];
        private int index;
        private BufferedInputStream in;
        private int total;

        public ScanReader(InputStream inputStream) {
            in = new BufferedInputStream(inputStream);
        }

        private int scan() {
            if (index >= total) {
                index = 0;
                try {
                    total = in.read(buf);
                } catch (Exception e) {
                    e.printStackTrace();
                }
                if (total <= 0) return -1;
            }
            return buf[index++];
        }

        public int scanInt() {
            int integer = 0;
            int n = scan();
            while (isWhiteSpace(n)) n = scan();
            int neg = 1;
            if (n == '-') {
                neg = -1;
                n = scan();
            }
            while (!isWhiteSpace(n)) {
                if (n >= '0' && n <= '9') {
                    integer *= 10;
                    integer += n - '0';
                    n = scan();
                }
            }
            return neg * integer;
        }

        private boolean isWhiteSpace(int n) {
            if (n == ' ' || n == '\n' || n == '\r' || n == '\t' || n == -1) return true;
            else return false;
        }

    }
}