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.*;
import java.math.*;
import java.lang.*;

public class Main {
    private static FastReader sc = new FastReader(System.in);
    private static OutputWriter out = new OutputWriter(System.out);
    private static int[] numDiv;

    public static void main(String[] args) throws Exception {
        int n = sc.nextInt();
        int q = sc.nextInt();
        long[] arr = new long[n];
        numDiv();
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }

        SegmentTree st = new SegmentTree(n, arr);
        TreeSet<Integer> notDone = new TreeSet<>();
        for (int i = 0; i < n; i++) notDone.add(i);

        while (q-- > 0) {
            int type = sc.nextInt();
            int l = sc.nextInt() - 1;
            int r = sc.nextInt() - 1;

            if (type == 1) {
                HashSet<Integer> done = new HashSet<>();
                for (int idx : notDone.subSet(l, r + 1)) {
                    st.update(idx, numDiv[(int) arr[idx]]);
                    arr[idx] = numDiv[(int) arr[idx]];
                    if (arr[idx] == 2 || arr[idx] == 1) {
                        done.add(idx);
                    }
                }
                notDone.removeAll(done);
            } else {
                out.printLine(st.query(l, r));
            }
        }
        out.close();
    }

    private static void numDiv() {
        numDiv = new int[(int) (1e6 + 5)];
        for (int i = 1; i <= 1e6; i++) {
            for (int j = i; j <= 1e6; j += i) {
                numDiv[j]++;
            }
        }
    }
}

class SegmentTree {
    long[] st;
    long[] arr;
    int nodes;
    int n;

    public SegmentTree(int n, long[] arr) {
        nodes = 0;
        this.n = n;
        this.arr = new long[n];
        st = new long[4 * n + 10];
        for (int i = 0; i < n; i++) {
            this.arr[i] = arr[i];
        }
        build(0, 0, n - 1);
    }

    public void build(int node, int sl, int sr) {
        if (sl == sr) {
            st[node] = arr[sl];
            return;
        }
        int mid = (sl + sr) / 2;
        build(2 * node + 1, sl, mid);
        build(2 * node + 2, mid + 1, sr);
        st[node] = st[2 * node + 1] + st[2 * node + 2];
    }

    public long query(int ql, int qr) {
        return query(0, 0, n - 1, ql, qr);
    }

    private long query(int node, int sl, int sh, int ql, int qh) {
        if (ql > sh || qh < sl) return 0;
        if (ql <= sl && qh >= sh) return st[node];
        int mid = (sl + sh) / 2;
        return query(2 * node + 1, sl, mid, ql, qh) + query(2 * node + 2, mid + 1, sh, ql, qh);
    }

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

    private void update(int node, int sl, int sh, int pos, int val) {
        if (sl == sh) {
            st[node] = val;
            return;
        }
        int mid = (sl + sh) / 2, l, r;
        if (pos <= mid) {
            update(2 * node + 1, sl, mid, pos, val);
        } else {
            update(2 * node + 2, mid + 1, sh, pos, val);
        }
        st[node] = st[2 * node + 1] + st[2 * node + 2];
    }
}

class Node {
    long val;
    int l, r;

    public Node(long v, int left, int right) {
        val = v;
        l = left;
        r = right;
    }

    public String toString() {
        return "{" + val + " " + l + " " + r + "}";
    }
}

class FastReader {
    private boolean finished = false;

    private InputStream stream;
    private byte[] buf = new byte[1024];
    private int curChar;
    private int numChars;
    private SpaceCharFilter filter;

    public FastReader(InputStream stream) {
        this.stream = stream;
    }

    public int read() {
        if (numChars == -1) {
            throw new InputMismatchException();
        }
        if (curChar >= numChars) {
            curChar = 0;
            try {
                numChars = stream.read(buf);
            } catch (IOException e) {
                throw new InputMismatchException();
            }
            if (numChars <= 0) {
                return -1;
            }
        }

        return buf[curChar++];
    }

    public int peek() {
        if (numChars == -1) {
            return -1;
        }
        if (curChar >= numChars) {
            curChar = 0;
            try {
                numChars = stream.read(buf);
            } catch (IOException e) {
                return -1;
            }
            if (numChars <= 0) {
                return -1;
            }
        }
        return buf[curChar];
    }

    public int nextInt() {
        int c = read();
        while (isSpaceChar(c))
            c = read();
        int sgn = 1;
        if (c == '-') {
            sgn = -1;
            c = read();
        }
        int res = 0;
        do {
            if (c == ',') {
                c = read();
            }
            if (c < '0' || c > '9') {
                throw new InputMismatchException();
            }
            res *= 10;
            res += c - '0';
            c = read();
        } while (!isSpaceChar(c));
        return res * sgn;
    }

    public long nextLong() {
        int c = read();
        while (isSpaceChar(c))
            c = read();
        int sgn = 1;
        if (c == '-') {
            sgn = -1;
            c = read();
        }
        long res = 0;
        do {
            if (c < '0' || c > '9') {
                throw new InputMismatchException();
            }
            res *= 10;
            res += c - '0';
            c = read();
        } while (!isSpaceChar(c));
        return res * sgn;
    }

    public String nextString() {
        int c = read();
        while (isSpaceChar(c))
            c = read();
        StringBuilder res = new StringBuilder();
        do {
            res.appendCodePoint(c);
            c = read();
        } while (!isSpaceChar(c));
        return res.toString();
    }

    public boolean isSpaceChar(int c) {
        if (filter != null) {
            return filter.isSpaceChar(c);
        }
        return isWhitespace(c);
    }

    public static boolean isWhitespace(int c) {
        return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
    }

    private String readLine0() {
        StringBuilder buf = new StringBuilder();
        int c = read();
        while (c != '\n' && c != -1) {
            if (c != '\r') {
                buf.appendCodePoint(c);
            }
            c = read();
        }
        return buf.toString();
    }

    public String nextLine() {
        String s = readLine0();
        while (s.trim().length() == 0)
            s = readLine0();
        return s;
    }

    public String nextLine(boolean ignoreEmptyLines) {
        if (ignoreEmptyLines) {
            return nextLine();
        } else {
            return readLine0();
        }
    }

    public BigInteger nextBigInteger() {
        try {
            return new BigInteger(nextString());
        } catch (NumberFormatException e) {
            throw new InputMismatchException();
        }
    }

    public char nextCharacter() {
        int c = read();
        while (isSpaceChar(c))
            c = read();
        return (char) c;
    }

    public double nextDouble() {
        int c = read();
        while (isSpaceChar(c))
            c = read();
        int sgn = 1;
        if (c == '-') {
            sgn = -1;
            c = read();
        }
        double res = 0;
        while (!isSpaceChar(c) && c != '.') {
            if (c == 'e' || c == 'E') {
                return res * Math.pow(10, nextInt());
            }
            if (c < '0' || c > '9') {
                throw new InputMismatchException();
            }
            res *= 10;
            res += c - '0';
            c = read();
        }
        if (c == '.') {
            c = read();
            double m = 1;
            while (!isSpaceChar(c)) {
                if (c == 'e' || c == 'E') {
                    return res * Math.pow(10, nextInt());
                }
                if (c < '0' || c > '9') {
                    throw new InputMismatchException();
                }
                m /= 10;
                res += (c - '0') * m;
                c = read();
            }
        }
        return res * sgn;
    }

    public boolean isExhausted() {
        int value;
        while (isSpaceChar(value = peek()) && value != -1)
            read();
        return value == -1;
    }

    public String next() {
        return nextString();
    }

    public SpaceCharFilter getFilter() {
        return filter;
    }

    public void setFilter(SpaceCharFilter filter) {
        this.filter = filter;
    }

    public interface SpaceCharFilter {
        public boolean isSpaceChar(int ch);
    }
}

class OutputWriter {
    private final PrintWriter writer;

    public OutputWriter(OutputStream outputStream) {
        writer = new PrintWriter(new BufferedWriter(new OutputStreamWriter(outputStream)));
    }

    public OutputWriter(Writer writer) {
        this.writer = new PrintWriter(writer);
    }

    public void print(Object... objects) {
        for (int i = 0; i < objects.length; i++) {
            if (i != 0)
                writer.print(' ');
            writer.print(objects[i]);
        }
    }

    public void printLine(Object... objects) {
        print(objects);
        writer.println();
    }

    public void close() {
        writer.close();
    }

    public void flush() {
        writer.flush();
    }

}