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

public class Main {

    static class Solution extends Helper {
        static int[] memo;

        static int d(int n) {
            return memo[n];
        }

        public void solve(InputReader in, PrintWriter out) {
            memo = new int[(int) 1e6 + 2];
            for (int i = 1; i < (int) 1e6 + 2; i++)
                for (int j = i; j < (int) 1e6 + 2; j += i)
                    memo[j]++;
            int n = in.getInt(), m = in.getInt();
            int[] a = new int[n];
            for (int i = 0; i < n; i++) a[i] = in.getInt();
            Seg seg = new Seg(a);
            while (m-- > 0) {
                int t = in.getInt(), l = in.getInt() - 1, r = in.getInt() - 1;
                if (t == 1) seg.update(1, 0, n - 1, l, r);
                else out.println(seg.query(1, 0, n - 1, l, r));
            }
        }

        static class Seg {
            int[] a;
            long[] tree;
            boolean[] finished;
            int n;

            Seg(int[] aa) {
                a = aa;
                n = a.length;
                tree = new long[n << 2];
                finished = new boolean[n << 2];
                build(1, 0, n - 1);
            }

            void build(int node, int s, int e) {
                if (s == e) {
                    tree[node] = a[s];
                    finished[node] = a[s] <= 2;
                } else {
                    int mid = s + e >> 1;
                    build(node << 1, s, mid);
                    build(node << 1 | 1, mid + 1, e);
                    tree[node] = tree[node << 1] + tree[node << 1 | 1];
                    finished[node] = finished[node << 1] && finished[node << 1 | 1];
                }
            }

            void update(int node, int s, int e, int l, int r) {
                if (s > r || e < l) return;
                if (finished[node]) return;
                if (s == e) {
                    finished[node] = (tree[node] = d((int) tree[node])) <= 2;
                } else {
                    int mid = s + e >> 1;
                    update(node << 1, s, mid, l, r);
                    update(node << 1 | 1, mid + 1, e, l, r);
                    tree[node] = tree[node << 1] + tree[node << 1 | 1];
                    finished[node] = finished[node << 1] && finished[node << 1 | 1];
                }
            }

            long query(int node, int s, int e, int l, int r) {
                if (s > r || e < l) return 0;
                if (s >= l && e <= r) return tree[node];
                int mid = s + e >> 1;
                return query(node << 1, s, mid, l, r) + query(node << 1 | 1, mid + 1, e, l, r);
            }

        }
    }

    public static void main(String[] args) {
        Helper helper = new Helper();
        helper.RUN();
    }

    public static class Helper {

        public boolean online_judge = System.getProperty("ONLINE_JUDGE") != null;
        public static final int INF = Integer.MAX_VALUE;
        public static final long INFF = Long.MAX_VALUE;
        public static final double PI = Math.PI;

        public void RUN() {
            Solution solution = new Solution();
            InputStream inputStream = System.in;
            if (!online_judge)
                try {
                    inputStream = online_judge ? System.in : new FileInputStream("./src/com/company/in.txt");
                } catch (FileNotFoundException e) {
                    e.printStackTrace();
                }
            OutputStream outputStream = System.out;
            InputReader in = new InputReader(inputStream);
            PrintWriter out = new PrintWriter(outputStream);

            if (!online_judge) {
                int cur_ans = 1;
                while (true) {

                    try {
                        if (!in.bufferedReader.ready()) break;
                    } catch (IOException e) {
                        e.printStackTrace();
                    }
                    out.print("It is test#" + cur_ans + "\n\n");
                    solution.solve(in, out);
                    out.print("\n\n");
                    cur_ans++;
                    try {
                        COPY_FILE(inputStream, outputStream, in, out);
                    } catch (IOException e) {
                        e.printStackTrace();
                    }
                }
            } else
                solution.solve(in, out);
            out.close();
            out.flush();
        }

        private void COPY_FILE(InputStream inputStream, OutputStream outputStream, InputReader in, PrintWriter out) throws IOException {
            inputStream = new FileInputStream("./src/com/company/Main.java");
            outputStream = new FileOutputStream("./src/com/company/output/Main.java");
            in = new InputReader(inputStream);
            out = new PrintWriter(outputStream);
            String line = "";
            while (in.bufferedReader.ready()) {
                line = in.getLine();
                if(!line.equals("package com.company;"))
                    out.write(line + "\n");
            }
            out.close();
        }
    }

    public static class InputReader {
        private BufferedReader bufferedReader;
        private StringTokenizer stringTokenizer;
        private String line;

        public InputReader(InputStream inputStream) {
            bufferedReader = new BufferedReader(new InputStreamReader(inputStream));
            stringTokenizer = null;
        }

        public String getLine() {
            line = "";
            try {
                line = bufferedReader.readLine();
            } catch (IOException e) {
                e.printStackTrace();
            }
            return line;
        }

        public String getString() {
            while (stringTokenizer == null || !stringTokenizer.hasMoreTokens()) {
                try {
                    stringTokenizer = new StringTokenizer(bufferedReader.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }
            return stringTokenizer.nextToken();
        }

        public int getInt() {
            return Integer.parseInt(getString());
        }

        public long getLong() {
            return Long.parseLong(getString());
        }

        public double getDouble() {
            return Double.parseDouble(getString());
        }
    }
}