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.*;

import static java.lang.Math.floor;
import static java.lang.Math.log;
import static java.lang.Math.sqrt;


import java.util.List;

public class Main {

    public static void main(String[] args) throws Exception {

        new Main().go();
    }

    PrintWriter out;
    InputReader in;
    BufferedReader br;

    Main() throws IOException {

        try {

            //br = new BufferedReader( new FileReader("input.txt") );
            //in = new Reader("input.txt");
            in = new InputReader("input.txt");
            out = new PrintWriter( new BufferedWriter(new FileWriter("output.txt")) );
        }
        catch (Exception e) {

            //br = new BufferedReader( new InputStreamReader( System.in ) );
            in = new InputReader();
            out = new PrintWriter( new BufferedWriter(new OutputStreamWriter(System.out)) );
        }
    }

    void go() throws Exception {

        int t = 1;
        while (t > 0) {
            solve();
            //out.println();
            t--;
        }

        out.flush();
        out.close();
    }


    int inf = 2000000000;
    int mod = 1000000007;
    double eps = 0.000000001;

    int n;
    int m;

    int[] d = new int[1000010];

    void solve() throws IOException {

        n = in.nextInt();
        int m = in.nextInt();

        for (int i = 1; i <= 1000000; i++)
            for (int j = i; j <= 1000000; j += i)
                d[j]++;

        ST t = new ST(n);

        for (int i = 0; i < n; i++) {
            int x = in.nextInt();
            t.updMin(1, 0, n-1, i, x);
            t.addSum(1, 0, n-1, i, x);
        }

        for (int i = 0; i < m; i++) {

            int c = in.nextInt();
            int l = in.nextInt()-1;
            int r = in.nextInt()-1;

            if (c == 2) {
                out.println(t.getSum(1, 0, n-1, l, r));
            }
            else {
                t.updateSum(1, 0, n-1, l, r);
            }
        }
    }

    class ST {

        int[] tmin;
        long[] tsum;

        ST(int n) {
            tmin = new int[4*n];
            tsum = new long[4*n];
        }

        void updMin(int v, int tl, int tr, int ind, int val) {

            if (tl == tr) {
                tmin[v] = val;
                return;
            }

            int tm = (tl + tr) >> 1;
            if (tm >= ind)
                updMin(v*2, tl, tm, ind, val);
            else
                updMin(v*2+1, tm+1, tr, ind, val);
            tmin[v] = Math.max(tmin[v*2], tmin[v*2+1]);
        }

        int getMax(int v, int tl, int tr, int l, int r) {

            if (l > r)
                return 0;

            int tm = (tl + tr) >> 1;

            if (tl == l && tr == r)
                return tmin[v];

            return Math.max(
                    getMax(v*2, tl, tm, l, Math.min(tm, r)),
                    getMax(v*2+1, tm+1, tr, Math.max(l, tm+1), r));
        }

        void updateSum(int v, int tl, int tr, int l, int r) {

            if (l > r)
                return;

            int min = tmin[v];
            if (min <= 2)
                return;

            if (tl == tr) {
                tsum[v] = d[(int)tsum[v]];
                updMin(1, 0, n-1, tl, (int)tsum[v]);
                return;
            }

            int tm = (tl + tr) >> 1;

            updateSum(v*2, tl, tm, l, Math.min(tm, r));
            updateSum(v*2+1, tm+1, tr, Math.max(tm+1, l), r);
            tsum[v] = tsum[v*2] + tsum[v*2+1];
        }

        long getSum(int v, int tl, int tr, int l, int r) {

            if (l > r)
                return 0;

            if (tl == l && tr == r) {
                return tsum[v];
            }

            int tm = (tl + tr) >> 1;

            long s1 = getSum(v*2, tl, tm, l, Math.min(tm, r));
            long s2 = getSum(v*2+1, tm+1, tr, Math.max(tm+1, l), r);
            return s1 + s2;
        }

        void addSum(int v, int tl, int tr, int ind, int val) {

            if (tl == tr) {
                tsum[v] = val;
                return;
            }

            int tm = (tl+tr) >> 1;

            if (tm >= ind)
                addSum(v*2, tl, tm, ind, val);
            else
                addSum(v*2+1, tm+1, tr, ind, val);

            tsum[v] = tsum[v*2] + tsum[v*2+1];
        }


    }

    class Pair implements Comparable<Pair>{

        int a;
        int b;

        Pair(int a, int b) {
            this.a = a;
            this.b = b;
        }

        public int compareTo(Pair p) {

            if (a > p.a) return 1;
            if (a < p.a) return -1;
            if (b > p.b) return -1;
            if (b < p.b) return 1;
            return 0;
        }
    }

    class Item {

        int a;
        int b;
        int c;

        Item(int a, int b, int c) {
            this.a = a;
            this.b = b;
            this.c = c;
        }

    }

    class Reader {

        BufferedReader  br;
        StringTokenizer tok;

        Reader(String file) throws IOException {
            br = new BufferedReader( new FileReader(file) );
        }

        Reader() throws IOException {
            br = new BufferedReader( new InputStreamReader(System.in) );
        }

        String next() throws IOException {

            while (tok == null || !tok.hasMoreElements())
                tok = new StringTokenizer(br.readLine());
            return tok.nextToken();
        }

        int nextInt() throws NumberFormatException, IOException {
            return Integer.valueOf(next());
        }

        long nextLong() throws NumberFormatException, IOException {
            return Long.valueOf(next());
        }

        double nextDouble() throws NumberFormatException, IOException {
            return Double.valueOf(next());
        }


        String nextLine() throws IOException {
            return br.readLine();
        }

    }

    class Parser {
        final private int BUFFER_SIZE = 1 << 18;
        private DataInputStream din;
        private byte[] buffer;
        private int bufferPointer, bytesRead;

        public Parser(InputStream in) {
            din = new DataInputStream(in);
            buffer = new byte[BUFFER_SIZE];
            bufferPointer = bytesRead =  0;
        }
        public String nextString(int maxSize) {
            byte[] ch = new byte[maxSize];
            int point =  0;
            try {
                byte c = read();
                while (c == ' ' || c == '\n' || c=='\r')
                    c = read();
                while (c != ' ' && c != '\n' && c!='\r') {
                    ch[point++] = c;
                    c = read();
                }
            } catch (Exception e) {}
            return new String(ch, 0,point);
        }
        public int nextInt() {
            int ret =  0;
            boolean neg;
            try {
                byte c = read();
                while (c <= ' ')
                    c = read();
                neg = c == '-';
                if (neg)
                    c = read();
                do {
                    ret = ret * 10 + c - '0';
                    c = read();
                } while (c > ' ');

                if (neg) return -ret;
            } catch (Exception e) {}
            return ret;
        }
        public long nextLong() {
            long ret =  0;
            boolean neg;
            try {
                byte c = read();
                while (c <= ' ')
                    c = read();
                neg = c == '-';
                if (neg)
                    c = read();
                do {
                    ret = ret * 10 + c - '0';
                    c = read();
                } while (c > ' ');

                if (neg) return -ret;
            } catch (Exception e) {}
            return ret;
        }
        private void fillBuffer() {
            try {
                bytesRead = din.read(buffer, bufferPointer =  0, BUFFER_SIZE);
            } catch (Exception e) {}
            if (bytesRead == -1) buffer[0] = -1;
        }

        private byte read() {
            if (bufferPointer == bytesRead) fillBuffer();
            return buffer[bufferPointer++];
        }
    }

    static class InputReader
    {
        final private int BUFFER_SIZE = 1 << 16;
        private DataInputStream din;
        private byte[] buffer;
        private int bufferPointer, bytesRead;

        public InputReader()
        {
            din = new DataInputStream(System.in);
            buffer = new byte[BUFFER_SIZE];
            bufferPointer = bytesRead = 0;
        }

        public InputReader(String file_name) throws IOException
        {
            din = new DataInputStream(new FileInputStream(file_name));
            buffer = new byte[BUFFER_SIZE];
            bufferPointer = bytesRead = 0;
        }

        public String readLine() throws IOException
        {
            byte[] buf = new byte[64]; // line length
            int cnt = 0, c;
            while ((c = read()) != -1)
            {
                if (c == '\n')
                    break;
                buf[cnt++] = (byte) c;
            }
            return new String(buf, 0, cnt);
        }

        public int nextInt() throws IOException
        {
            int ret = 0;
            byte c = read();
            while (c <= ' ')
                c = read();
            boolean neg = (c == '-');
            if (neg)
                c = read();
            do
            {
                ret = ret * 10 + c - '0';
            }  while ((c = read()) >= '0' && c <= '9');

            if (neg)
                return -ret;
            return ret;
        }

        public long nextLong() throws IOException
        {
            long ret = 0;
            byte c = read();
            while (c <= ' ')
                c = read();
            boolean neg = (c == '-');
            if (neg)
                c = read();
            do {
                ret = ret * 10 + c - '0';
            }
            while ((c = read()) >= '0' && c <= '9');
            if (neg)
                return -ret;
            return ret;
        }

        public double nextDouble() throws IOException
        {
            double ret = 0, div = 1;
            byte c = read();
            while (c <= ' ')
                c = read();
            boolean neg = (c == '-');
            if (neg)
                c = read();

            do {
                ret = ret * 10 + c - '0';
            }
            while ((c = read()) >= '0' && c <= '9');

            if (c == '.')
            {
                while ((c = read()) >= '0' && c <= '9')
                {
                    ret += (c - '0') / (div *= 10);
                }
            }

            if (neg)
                return -ret;
            return ret;
        }

        private void fillBuffer() throws IOException
        {
            bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
            if (bytesRead == -1)
                buffer[0] = -1;
        }

        private byte read() throws IOException
        {
            if (bufferPointer == bytesRead)
                fillBuffer();
            return buffer[bufferPointer++];
        }

        public void close() throws IOException
        {
            if (din == null)
                return;
            din.close();
        }
    }









}