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.math.BigInteger;
import java.util.*;
import java.util.concurrent.atomic.AtomicIntegerArray;

public class Solution {

    public static void main(String[] args) throws Exception {
        MyReader reader = new MyReader(System.in);
//        MyReader reader = new MyReader(new FileInputStream("input.txt"));
        MyWriter writer = new MyWriter(System.out);
        new Solution().run(reader, writer);
        writer.close();
    }

    private void run(MyReader reader, MyWriter writer) throws Exception {
        int n = reader.nextInt();
        int m = reader.nextInt();
        int[] a = reader.nextIntArray(n);
        for (int i = 1; i < t; i++) {
            for (int j = i; j < t; j += i) {
                dd[j]++;
            }
        }
        for (int i = ww; i < ww * 2; i++) {
            tree[i] = new Node(i - ww < a.length ? a[i - ww] : 0, i - ww, i - ww, i - ww >= a.length || a[i - ww] <= 2);
            tree[i].sum = tree[i].a;
        }
        for (int i = ww - 1; i > 0; i--) {
            Node l = tree[2 * i];
            Node r = tree[2 * i + 1];
            tree[i] = new Node(0, l.l, r.r, l.c && r.c);
            tree[i].sum = l.sum + r.sum;
        }
        for (int i = 0; i < m; i++) {
            int q = reader.nextInt();
            int x = reader.nextInt() - 1;
            int y = reader.nextInt() - 1;
            if (q == 1) {
                f(1, x, y);
            } else {
                System.out.println(sum(1, x, y));
            }
        }
    }

    int t = 1_000_001;
    int[] dd = new int[t];
    int ww = 1 << 19;
    Node[] tree = new Node[ww * 2];

    private void f(int i, int l, int r) {
        Node node = tree[i];
        if (node.c || node.l > r || node.r < l) {
            return;
        }
        if (i >= ww) {
            node.a = dd[node.a];
            node.sum = node.a;
            if (node.a <= 2) {
                node.c = true;
            }
        } else {
            f(2 * i, l, r);
            f(2 * i + 1, l, r);
            node.sum = tree[2 * i].sum + tree[2 * i + 1].sum;
            node.c = tree[2 * i].c && tree[2 * i + 1].c;
        }
    }

    private long sum(int i, int l, int r) {
        Node node = tree[i];
        if (l <= node.l && node.r <= r) {
            return node.sum;
        }
        if (node.l > r || node.r < l) {
            return 0;
        }
        return sum(2 * i, l, r) + sum(2 * i + 1, l, r);
    }

    class Node {
        int a;
        int l;
        int r;
        long sum;
        boolean c;

        public Node(int a, int l, int r, boolean c) {
            this.a = a;
            this.l = l;
            this.r = r;
            this.c = c;
        }
    }

    static class MyReader {

        final BufferedInputStream in;
        final int bufSize = 1 << 16;
        final byte buf[] = new byte[bufSize];
        int i = bufSize;
        int k = bufSize;
        boolean end = false;
        final StringBuilder str = new StringBuilder();

        MyReader(InputStream in) {
            this.in = new BufferedInputStream(in, bufSize);
        }

        int nextInt() throws IOException {
            return (int) nextLong();
        }

        int[] nextIntArray(int n) throws IOException {
            int[] m = new int[n];
            for (int i = 0; i < n; i++) {
                m[i] = nextInt();
            }
            return m;
        }

        int[][] nextIntMatrix(int n, int m) throws IOException {
            int[][] a = new int[n][0];
            for (int j = 0; j < n; j++) {
                a[j] = nextIntArray(m);
            }
            return a;
        }

        long nextLong() throws IOException {
            int c;
            long x = 0;
            boolean sign = true;
            while ((c = nextChar()) <= 32) ;
            if (c == '-') {
                sign = false;
                c = nextChar();
            }
            if (c == '+') {
                c = nextChar();
            }
            while (c >= '0') {
                x = x * 10 + (c - '0');
                c = nextChar();
            }
            return sign ? x : -x;
        }

        long[] nextLongArray(int n) throws IOException {
            long[] m = new long[n];
            for (int i = 0; i < n; i++) {
                m[i] = nextLong();
            }
            return m;
        }

        int nextChar() throws IOException {
            if (i == k) {
                k = in.read(buf, 0, bufSize);
                i = 0;
            }
            return i >= k ? -1 : buf[i++];
        }

        String nextString() throws IOException {
            if (end) {
                return null;
            }
            str.setLength(0);
            int c;
            while ((c = nextChar()) <= 32 && c != -1) ;
            if (c == -1) {
                end = true;
                return null;
            }
            while (c > 32) {
                str.append((char) c);
                c = nextChar();
            }
            return str.toString();
        }

        String nextLine() throws IOException {
            if (end) {
                return null;
            }
            str.setLength(0);
            int c = nextChar();
            while (c != '\n' && c != '\r' && c != -1) {
                str.append((char) c);
                c = nextChar();
            }
            if (c == -1) {
                end = true;
                if (str.length() == 0) {
                    return null;
                }
            }
            if (c == '\r') {
                nextChar();
            }
            return str.toString();
        }

        char[] nextCharArray() throws IOException {
            return nextString().toCharArray();
        }

        char[][] nextCharMatrix(int n) throws IOException {
            char[][] a = new char[n][0];
            for (int i = 0; i < n; i++) {
                a[i] = nextCharArray();
            }
            return a;
        }
    }

    static class MyWriter {

        final BufferedOutputStream out;
        final int bufSize = 1 << 16;
        final byte buf[] = new byte[bufSize];
        int i = 0;
        final byte c[] = new byte[30];
        static final String newLine = System.getProperty("line.separator");

        MyWriter(OutputStream out) {
            this.out = new BufferedOutputStream(out, bufSize);
        }

        void print(long x) throws IOException {
            int j = 0;
            if (i + 30 >= bufSize) {
                flush();
            }
            if (x < 0) {
                buf[i++] = (byte) ('-');
                x = -x;
            }
            while (j == 0 || x != 0) {
                c[j++] = (byte) (x % 10 + '0');
                x /= 10;
            }
            while (j-- > 0)
                buf[i++] = c[j];
        }

        void print(int[] m) throws IOException {
            for (int a : m) {
                print(a);
                print(' ');
            }
        }

        void print(long[] m) throws IOException {
            for (long a : m) {
                print(a);
                print(' ');
            }
        }

        void print(String s) throws IOException {
            for (int i = 0; i < s.length(); i++) {
                print(s.charAt(i));
            }
        }

        void print(char x) throws IOException {
            if (i == bufSize) {
                flush();
            }
            buf[i++] = (byte) x;
        }

        void print(char[] m) throws IOException {
            for (char c : m) {
                print(c);
            }
        }

        void println(String s) throws IOException {
            print(s);
            println();
        }

        void println() throws IOException {
            print(newLine);
        }

        void flush() throws IOException {
            out.write(buf, 0, i);
            out.flush();
            i = 0;
        }

        void close() throws IOException {
            flush();
            out.close();
        }
    }
}