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 Jenish
 */
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);
        Sum_and_replace solver = new Sum_and_replace();
        solver.solve(1, in, out);
        out.close();
    }

    static class Sum_and_replace {
        int[] arr;
        long[][] tree;
        long[] div;
        int[] lazy;

        void pre() {

            div = new long[1000005];

            for (int i = 1; i <= 1000000; i++) {
                for (int j = i; j <= 1000000; j += i) {
                    div[j]++;
                }
            }

        }

        public void solve(int testNumber, ScanReader in, PrintWriter out) {
            int n = in.scanInt();
            int m = in.scanInt();
            arr = new int[n + 5];
            tree = new long[(4 * n) + 5][19];
            lazy = new int[(4 * n) + 5];
            for (int i = 1; i <= n; i++) {
                arr[i] = in.scanInt();
            }

            pre();
            build_tre(1, 1, n);

            while (m-- > 0) {
                int type = in.scanInt();
                int l = in.scanInt();
                int r = in.scanInt();
                if (type == 1) {
                    updateRagne(1, 1, n, l, r);
                } else {
                    out.println(query(1, 1, n, l, r));
                }
            }
        }

        void updateLazy(int node, int start, int end, int val) {
            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 * 2] += val;
                    lazy[(node * 2) + 1] += val;
                }
                lazy[node] = 0;
            }
        }

        void build_tre(int node, int start, int end) {
            if (start == end) {
                tree[node][0] = arr[start];
                for (int i = 1; i <= 7; i++)
                    tree[node][i] = div[(int) tree[node][i - 1]];
            } else {
                int mid = (start + end) / 2;
                build_tre(node * 2, start, mid);
                build_tre((node * 2) + 1, mid + 1, end);
                for (int i = 0; i <= 7; i++)
                    tree[node][i] = tree[node * 2][i] + tree[(node * 2) + 1][i];
            }
        }

        void updateRagne(int node, int start, int end, int l, int r) {
            updateLazy(node, start, end, lazy[node]);


            if (tree[node][0] == (end - start + 1))
                return;

            if (start > end || l > end || r < start) return;

            if (l <= start && end <= r) {
                updateLazy(node, start, end, 1);
                return;
            }

            int mid = (start + end) / 2;
            updateRagne(node * 2, start, mid, l, r);
            updateRagne((node * 2) + 1, mid + 1, end, l, r);
            for (int i = 0; i <= 7; i++)
                tree[node][i] = tree[node * 2][i] + tree[(node * 2) + 1][i];

        }

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

    }

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

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

        private int scan() {
            if (index >= Total_Char) {
                index = 0;
                try {
                    Total_Char = in.read(buf);
                } catch (Exception e) {
                    e.printStackTrace();
                }
                if (Total_Char <= 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;
        }

    }
}