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 sun.reflect.generics.tree.Tree;

import java.io.*;
import java.lang.reflect.Array;
import java.math.BigInteger;
import java.util.*;
import java.util.Map.Entry;

public class Template {

    class Edge{
        int to;
        int num;
        Edge(int to, int num){
            this.to = to;
            this.num = num;
        }
    }

    class Vertex{
        int x, y;
        Vertex(int x, int y){
            this.x = x;
            this.y = y;
        }

    }
    String fileName = "";
    int MODULO = 1000*1000*1000+7;
    ArrayList<Integer>[] graph;
    void solve() throws IOException {
        simple_ints = new ArrayList<>();
        int size = 1000001;
        r = new boolean[size];
        for (int i = 2; i < size; i++) if (!r[i]) for (int j = 2; j * i < size; j++) r[i * j] = true;
        for (int i = 2; i < size; i++) if (!r[i]) simple_ints.add(i);
        d = new int[size];
        for (int i = 2; i < size; i++) d[i] = getD(0, i);
        d[1] = 1;
        int n = readInt();
        int m = readInt();
        int[] a = readIntArray(n);
        TreeSet<Integer> st = new TreeSet<>();
        for (int i = -1; i < n; i++) st.add(i);
        for (int i = 0; i < n; i++) if (a[i] <= 2) st.remove(i);
        ArrayDeque<Integer> queue = new ArrayDeque<>();
        Fenwik fen = new Fenwik(a);
        while (m-- > 0) {
            int type = readInt();
            int lo = readInt() - 1;
            int hi = readInt() - 1;
            if (type == 1) {
                int cur = st.floor(hi);
                while (cur >= lo) {
                    int pref = a[cur];
                    a[cur] = d[a[cur]];
                    fen.inc(cur, a[cur] - pref);
                    st.remove(cur);
                    if (a[cur] > 2) queue.add(cur);
                    cur = st.floor(hi);
                }
                while (queue.size() > 0) st.add(queue.poll());
            } else out.println(fen.getSum(hi) - (lo > 0 ? fen.getSum(lo - 1) : 0));
        }
    }

    int[] d;
    ArrayList<Integer> simple_ints;
    boolean[] r;

    int getD(int index, int value) {
        if (d[value] != 0) return d[value];
        int k = 1;
        while (value % simple_ints.get(index) == 0) {
            k++;
            value /= simple_ints.get(index);
        }
        if (value == 1) return k;
        if (!r[value]) return (k << 1);
        int next = getD(index + 1, value);
        d[value] = next;
        k *= next;
        return k;
    }
    boolean isLower(char c){
        return c >= 'a' && c <= 'z';
    }

    ////////////////////////////////////////////////////////////
    class Pair{
        int num;
        int val;
        Pair(int num, int val ){
            this.num = num;
            this.val = val;
        }
    }
    /*
    class SegmentTree {
        int start = 0;
        int end = 0;
        long delta;
        int n;
        long result;
        long[] t;
        boolean[] lazy;
        int[] length;
        Pair[] segments;
        SegmentTree(int n, int[] a){
            this.n = n;
            t = new long[4*n];
            lazy = new boolean[4*n];
            length = new int[4*n];
            segments = new Pair[4*n];
            build(a, 1, 1, n);
        }

        void build(int[] a, int v, int tl, int tr){
            if(tl>tr) return;
            if(tl == tr){
                t[v] = a[tl];
                length[v] = 1;
                return;
            }
            int mid = (tl+tr)/2;
            build(a, 2*v, tl, mid);
            build(a, 2*v+1, mid+1, tr);
            length[v] = tr - tl +1;
            t[v] = t[2*v] + t[2*v+1];
        }
        void pushVertex(int v, int vLeft, int vRight){
            lazy[vLeft] += lazy[v];
            lazy[vRight] += lazy[v];
            lazy[v] = 0;
        }

        void updateVertex(int v, int vLeft, int vRight){
            t[v] = getSum(vLeft) + getSum(vRight);
        }

        long getSum(int v){
            return t[v] + lazy[v] * length[v];
        }

        void incSegment(int start, int end, long delta){
            this.start = start;
            this.end = end;
            this.delta = delta;
            incSegment(1, 1, n);
        }

        void incSegment(int v, int l, int r){
            if(start <= l && r <= end){
                lazy[v] += delta;
            }else{
                int mid = (r+l)/2;
                int vLeft = (v << 1);
                int vRight = vLeft + 1;
                pushVertex(v, vLeft, vRight);

                if(start <= mid) incSegment(vLeft, l, mid);
                if(end >= mid +1) incSegment(vRight, mid+1, r);

                updateVertex(v, vLeft, vRight);
            }
        }

        long getSegment(int start, int end){
            this.start = start;
            this.end = end;
            this.result = 0;
            getSegment(1, 1, n);
            return result;
        }
        void getSegment(int v, int l, int r){
            if(start <= l && r <= end){
                result += getSum(v);
            }else{
                int mid = (r+l)/2;
                int vLeft = (v << 1);
                int vRight = vLeft + 1;
                pushVertex(v, vLeft, vRight);

                if(start <= mid) getSegment(vLeft, l, mid);
                if(end >= mid +1) getSegment(vRight, mid+1, r);

                updateVertex(v, vLeft, vRight);
            }
        }
    }
*/
    class Fenwik {
        long[] t;
        int length;

        Fenwik(int[] a) {
            length = a.length + 100;
            t = new long[length];

            for (int i = 0; i < a.length; ++i) {
                inc(i, a[i]);
            }
        }

        void inc(int ind, int delta) {
            for (; ind < length; ind = ind | (ind + 1)) {
                t[ind] += delta;
            }
        }

        long getSum(int r) {
            long sum = 0;
            for (; r >= 0; r = (r & (r + 1)) - 1) {
                sum += t[r];
            }
            return sum;
        }
    }
    int gcd(int a, int b){
        return b == 0 ? a : gcd(b, a%b);
    }

    long binPow(long a, long b, long m) {
        if (b == 0) {
            return 1;
        }
        if (b % 2 == 1) {
            return ((a % m) * (binPow(a, b - 1, m) % m)) % m;
        } else {
            long c = binPow(a, b / 2, m);
            return (c * c) % m;
        }

    }

    public static void main(String[] args) throws NumberFormatException, IOException {
        // TODO Auto-generated method stub
        new Template().run();
    }

    void run() throws NumberFormatException, IOException {
        solve();
        out.close();
    };

    BufferedReader in;
    PrintWriter out;

    StringTokenizer tok;
    String delim = " ";
    Random rnd = new Random();

    Template() throws FileNotFoundException {
        try {
            in = new BufferedReader(new FileReader("input.txt"));
            out = new PrintWriter("output.txt");
        } catch (Exception e) {
            if (fileName.isEmpty()) {
                in = new BufferedReader(new InputStreamReader(System.in));
                out = new PrintWriter(System.out);
            } else {
                in = new BufferedReader(new FileReader(fileName + ".in"));
                out = new PrintWriter(fileName + ".out");
            }

        }
        tok = new StringTokenizer("");
    }

    String readLine() throws IOException {
        return in.readLine();
    }

    String readString() throws IOException {
        while (!tok.hasMoreTokens()) {
            String nextLine = readLine();
            if (null == nextLine) {
                return null;
            }

            tok = new StringTokenizer(nextLine);
        }
        return tok.nextToken();
    }

    int readInt() throws NumberFormatException, IOException {
        return Integer.parseInt(readString());
    }
    byte readByte() throws NumberFormatException, IOException {
        return Byte.parseByte(readString());
    }
    int[] readIntArray (int n) throws NumberFormatException, IOException {
        int[] a = new int[n];
        for(int i=0; i<n; ++i){
            a[i] = readInt();
        }
        return a;
    }
    long readLong() throws NumberFormatException, IOException {
        return Long.parseLong(readString());
    }

    double readDouble() throws NumberFormatException, IOException {
        return Double.parseDouble(readString());
    }
}