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.Arrays;
import java.util.Objects;
import java.util.StringTokenizer;

public final class ProblemF {
    public static void main(String[] args) throws IOException {
        final FastIn in = FastIn.fromSystemIn();
        final int n = in.nextInt();
        final int m = in.nextInt();
        long[] array = in.nextLongArray(n);
//        final SegmentTree st = new SegmentTree(array);
        final SegmentTreeEager segmentTreeEager = new SegmentTreeEager(array);
        final PrintWriter pw = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));
        for (int i = 0; i < m; i++) {
            final int opCode = in.nextInt();
            final int l = in.nextInt();
            final int r = in.nextInt();
            switch (opCode) {
                case 1:
                    //replace
//                    st.replace(l, r);
                    segmentTreeEager.replace(l, r);
                    break;
                case 2:
                    //sum
//                    System.out.println(st.sum(l, r));
                    pw.println(segmentTreeEager.sum(l, r));
                    break;
            }
        }
        pw.flush();
        pw.close();
    }

    private static final int[] dArray;
    static {
        dArray = new int[1_000_001];
        Arrays.fill(dArray, 2);
        dArray[1] = 1;
        for (int i = 2; i < dArray.length; i++) {
            for (int j = i + i; j < dArray.length; j += i) {
                dArray[j]++;
            }
        }

    }

    private static final class SegmentTreeEager {
        private final long[] sum;
        private final boolean[] hasOnlyFixedPoints;

        SegmentTreeEager(final long[] array) {
            final boolean isPowerOf2 = (array.length & (array.length- 1)) == 0;
            final int treeSize = isPowerOf2 ? array.length << 1 : Integer.highestOneBit(array.length) << 2;
            this.sum = new long[treeSize];
            this.hasOnlyFixedPoints = new boolean[treeSize];
            System.arraycopy(array, 0, sum, treeSize / 2, array.length);
            for (int i = treeSize / 2; i < treeSize / 2 + array.length; i++) {
                if (sum[i] <= 2) {
                    hasOnlyFixedPoints[i] = true;
                }
            }
            for (int i = treeSize / 2 - 1; i > 0; i--) {
                sum[i] = sum[left(i)] + sum[right(i)];
                hasOnlyFixedPoints[i] = hasOnlyFixedPoints[left(i)] && hasOnlyFixedPoints[right(i)];
            }
        }

        void replace(int l, int r) {
            replace(1, 1, sum.length / 2, l, r);
        }

        void replace(int p, int pLeft, int pRight, int qLeft, int qRight) {
            if (qRight < pLeft || pRight < qLeft) {
                return;
            } else if (hasOnlyFixedPoints[p]) {
                return;
            } else if (pLeft == pRight) {//should be length 1, single element
                sum[p] = dArray[(int) sum[p]];
                hasOnlyFixedPoints[p] = sum[p] <= 2;
            } else {
                final int lEnd = pLeft + (pRight - pLeft) / 2;
                replace(left(p), pLeft , lEnd , qLeft, qRight);
                replace(right(p), lEnd + 1, pRight, qLeft, qRight);
                sum[p] = sum[left(p)] + sum[right(p)];
                hasOnlyFixedPoints[p] = hasOnlyFixedPoints[left(p)] && hasOnlyFixedPoints[right(p)];
            }
        }

        long sum(int l, int r) {
            return sum(1, 1, sum.length / 2, l, r);
        }

        long sum(int p, int pLeft, int pRight, int qLeft, int qRight) {
            if (qRight < pLeft || pRight < qLeft) {
                return 0L;
            } else if (qLeft <= pLeft && pRight <= qRight) {
                return sum[p];
            } else {
                final int lEnd = pLeft + (pRight - pLeft) / 2;
                return sum(left(p), pLeft, lEnd, qLeft, qRight) + sum(right(p), lEnd + 1, pRight, qLeft, qRight);
            }
        }

        private static int left(int p) {
            return p * 2;
        }

        private static int right(int p) {
            return p * 2 + 1;
        }

    }

    private static final class SegmentTree {
        private final long[] data;
        private final int[] repCount;
        private final boolean[] isLazy;
        private final int n;

        SegmentTree(final long[] array) {
            final boolean isPowerOf2 = (array.length & (array.length - 1)) == 0;
            final int treeSize;
            if (isPowerOf2) {
                treeSize = array.length << 1;
            } else {
                treeSize = Integer.highestOneBit(array.length) << 2;
            }
            this.data = new long[treeSize];
            this.repCount = new int[treeSize];
            this.isLazy = new boolean[treeSize];
            this.n = array.length;
            System.arraycopy(array, 0, data, treeSize / 2, array.length);
            for (int i = treeSize / 2 - 1; i > 0; i--) {
                data[i] = data[left(i)] + data[right(i)];
            }
        }

        private static int left(final int p) {
            return p * 2;
        }

        private static int right(final int p) {
            return p * 2 + 1;
        }

        private static int leftEnd(final int left, final int right) {
            return left + (right - left) / 2;
        }

        private static int rightStart(final int left, final int right) {
            return leftEnd(left, right) + 1;
        }

        private void replace(int left, int right) {
            replace(1, 1, n, left, right);
        }

        private void replace(int p, int pLeft, int pRight, int qLeft, int qRight) {
            if (qRight < pLeft || pRight < qLeft) {
                return;
            } else if (qLeft <= pLeft && pRight <= qRight) {
                repCount[p]++;
                isLazy[p] = true;
            } else {
                isLazy[left(p)] = true;
                repCount[left(p)] += repCount[p];
                replace(left(p), pLeft, leftEnd(pLeft, pRight), qLeft, qRight);

                isLazy[right(p)] = true;
                repCount[right(p)] += repCount[p];
                replace(right(p), rightStart(pLeft, pRight), pRight, qLeft, qRight);

                isLazy[p] = true;
                repCount[p] = 0;
            }
        }

        private long sum(int left, int right) {
            return sum(1, 1, n, left, right);
        }

        private long sum(int p, int pLeft, int pRight, int qLeft, int qRight) {
            if (qRight < pLeft || pRight < qLeft) {
                return 0;
            } else if (left(p) > data.length) {
                for (; repCount[p] > 0; repCount[p]--) {
                    final int value = (int) data[p];
                    final int dValue = dArray[value];
                    if (value == dValue) {
                        break;
                    }
                    data[p] = dValue;
                }
                isLazy[p] = false;
                return data[p];
            } else if (qLeft <= pLeft && pRight <= qRight) {
                if (isLazy[p]) {
                    isLazy[left(p)] = true;
                    repCount[left(p)] += repCount[p];

                    isLazy[right(p)] = true;
                    repCount[right(p)] += repCount[p];

                    isLazy[p] = false;
                    repCount[p] = 0;

                    data[p] = 0;
                    data[p] += sum(left(p), pLeft, leftEnd(pLeft, pRight), qLeft, qRight);
                    data[p] += sum(right(p), rightStart(pLeft, pRight), pRight, qLeft, qRight);
                }
                return data[p];
            } else {
                if (isLazy[p]) {
                    isLazy[left(p)] = true;
                    repCount[left(p)] += repCount[p];

                    isLazy[right(p)] = true;
                    repCount[right(p)] += repCount[p];

                    isLazy[p] = false;
                    repCount[p] = 0;
                }
                long ret =  0;
                ret += sum(left(p), pLeft, leftEnd(pLeft, pRight), qLeft, qRight);
                ret += sum(right(p), rightStart(pLeft, pRight), pRight, qLeft, qRight);
                data[p] = data[left(p)] + data[right(p)];
                return ret;
            }
        }

    }


    private static final class FastIn {
        private final BufferedReader br;
        private StringTokenizer tokenizer = null;

        private FastIn(final InputStream inputStream) {
            br = new BufferedReader(new InputStreamReader(inputStream));
        }

        static FastIn fromInputStream(final InputStream inputStream) {
            Objects.requireNonNull(inputStream);
            return new FastIn(inputStream);
        }

        static FastIn fromSystemIn() {
            return FastIn.fromInputStream(System.in);
        }

        private StringTokenizer tokenizer() throws IOException {
            if (tokenizer == null || !tokenizer.hasMoreTokens()) {
                final String nextLine = br.readLine();
                tokenizer = new StringTokenizer(nextLine);
            }
            return tokenizer;
        }

        private String nextToken() throws IOException {
            return tokenizer().nextToken();
        }

        int nextInt() throws IOException {
            return Integer.parseInt(nextToken());
        }

        long nextLong() throws IOException {
            return Long.parseLong(nextToken());
        }

        int[] nextIntArray(final int size) throws IOException {
            final int[] array = new int[size];
            for (int i = 0; i < array.length; i++) {
                array[i] = nextInt();
            }
            return array;
        }

        long[] nextLongArray(final int size) throws IOException {
            assert size >= 0 : "size must be non-negative";
            final long[] array = new long[size];
            for (int i = 0; i < array.length; i++) {
                array[i] = nextLong();
            }
            return array;
        }

        String nextString() throws IOException {
            return nextToken();
        }
    }

    private static final class FastOut {
        private final PrintWriter pw;

        private FastOut(final OutputStream outputStream) {
            pw = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
        }

        static FastOut toSystemOut() {
            return fromOutputStream(System.out);
        }

        static FastOut fromOutputStream(final OutputStream outputStream) {
            Objects.requireNonNull(outputStream);
            return new FastOut(outputStream);
        }

        void prinltn(final String s) {
            pw.println(s);
        }

        void flush() {
            pw.flush();
        }

        void close() {
            pw.close();
        }
    }
}