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:
/*
Keep solving problems.
*/

import java.util.*;
import java.io.*;

public class CFF {

    BufferedReader br;
    PrintWriter out;
    StringTokenizer st;
    boolean eof;
    final long MOD = 1000L * 1000L * 1000L + 7;
    int[] dx = {0, -1, 0, 1};
    int[] dy = {1, 0, -1, 0};
    private static final String yes = "YES";
    private static final String no = "NO";

    int arr[];
    long maxTree[];
    long sumTree[];
    void build_tree(int node, int nodeStartIndex, int nodeEndIndex) {
        if(nodeStartIndex > nodeEndIndex) return; // Out of range
        if(nodeStartIndex == nodeEndIndex) { // Leaf node
            maxTree[node] = arr[nodeStartIndex]; // Init value
            sumTree[node] = arr[nodeStartIndex]; // Init value
            return;
        }

        build_tree(node * 2, nodeStartIndex, (nodeStartIndex + nodeEndIndex) / 2); // Init left child
        build_tree(node * 2 + 1, 1 + (nodeStartIndex + nodeEndIndex) / 2, nodeEndIndex); // Init right child
        sumTree[node] = sumTree[node * 2] +  sumTree[node * 2 + 1]; // Init root value
        maxTree[node] = Math.max(maxTree[node * 2], maxTree[node * 2 + 1]); // Init root value
    }

    /**
     * Increment elements within range [queryStartIndex, queryEndIndex] with value
     */
    void update_tree(int node, int nodeStartIndex, int nodeEndIndex, int queryStartIndex, int queryEndIndex) {
        if(nodeStartIndex > nodeEndIndex || nodeStartIndex > queryEndIndex || nodeEndIndex < queryStartIndex) // Current segment is not within range [i, j]
            return;
        if(nodeStartIndex >= queryStartIndex && nodeEndIndex <= queryEndIndex) { // Segment is fully within range
            if (maxTree[node] <= 2) {
                return;
            }
            if (nodeStartIndex == nodeEndIndex) {
                arr[nodeStartIndex] = seive[arr[nodeStartIndex]];
                maxTree[node] = arr[nodeStartIndex]; // Init value
                sumTree[node] = arr[nodeStartIndex]; // Init value
                return;
            }
        }

        update_tree(node * 2, nodeStartIndex, (nodeStartIndex + nodeEndIndex) / 2, queryStartIndex, queryEndIndex); // Updating left child
        update_tree(node * 2 + 1, 1 + (nodeStartIndex + nodeEndIndex) / 2, nodeEndIndex, queryStartIndex, queryEndIndex); // Updating right child

        sumTree[node] = sumTree[node * 2] +  sumTree[node * 2 + 1]; // Init root value
        maxTree[node] = Math.max(maxTree[node * 2], maxTree[node * 2 + 1]); // Init root value
    }

    /**
     * Query tree to get max element value within range [queryStartIndex, queryEndIndex]
     */
    long query_tree(int node, int nodeStartIndex, int nodeEndIndex, int queryStartIndex, int queryEndIndex) {
        if(nodeStartIndex > nodeEndIndex || nodeStartIndex > queryEndIndex || nodeEndIndex < queryStartIndex) return 0; // Out of range
        if(nodeStartIndex >= queryStartIndex && nodeEndIndex <= queryEndIndex) {
            return sumTree[node];
        }

        long q1 = query_tree(node * 2, nodeStartIndex, (nodeStartIndex + nodeEndIndex) / 2, queryStartIndex, queryEndIndex); // Query left child
        long q2 = query_tree(1 + node * 2, 1 + (nodeStartIndex + nodeEndIndex) / 2, nodeEndIndex, queryStartIndex, queryEndIndex); // Query right child

        return q1 + q2;
    }

    int len = 1000010;
//    int len = 100;
    int[] seive = new int[1 + len];
    void solve() throws IOException {
        int n = nextInt();
        int m = nextInt();
        Arrays.fill(seive, 1);
        for (int i = 2; i <= len; i++) {
            for (int j = 1; j * i <= len; j++) {
                seive[j * i]++;
            }
        }

        arr = nextIntArr(n);
        sumTree = new long[5 * n];
        maxTree = new long[5 * n];
        build_tree(1, 0, n - 1);
        for (int i = 0; i < m; i++) {
            int q = nextInt();
            int l = nextInt() - 1;
            int r = nextInt() - 1;
            if (q == 1) {
                update_tree(1, 0, n - 1, l, r);
            }
            else {
                long res = query_tree(1, 0, n - 1, l, r);
                outln(res);
            }
        }
    }

    void shuffle(int[] a) {
        int n = a.length;
        for(int i = 0; i < n; i++) {
            int r = i + (int) (Math.random() * (n - i));
            int tmp = a[i];
            a[i] = a[r];
            a[r] = tmp;
        }
    }

    long gcd(long a, long b) {
        while(a != 0 && b != 0) {
            long c = b;
            b = a % b;
            a = c;
        }
        return a + b;
    }

    private void outln(Object o) {
        out.println(o);
    }
    private void out(Object o) {
        out.print(o);
    }
    public CFF() throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        out = new PrintWriter(System.out);
        solve();
        out.close();
    }
    public static void main(String[] args) throws IOException {
        new CFF();
    }

    public long[] nextLongArr(int n) throws IOException{
        long[] res = new long[n];
        for(int i = 0; i < n; i++)
            res[i] = nextLong();
        return res;
    }
    public int[] nextIntArr(int n) throws IOException {
        int[] res = new int[n];
        for(int i = 0; i < n; i++)
            res[i] = nextInt();
        return res;
    }
    public String nextToken() {
        while (st == null || !st.hasMoreTokens()) {
            try {
                st = new StringTokenizer(br.readLine());
            } catch (Exception e) {
                eof = true;
                return null;
            }
        }
        return st.nextToken();
    }
    public String nextString() {
        try {
            return br.readLine();
        } catch (IOException e) {
            eof = true;
            return null;
        }
    }
    public int nextInt() throws IOException {
        return Integer.parseInt(nextToken());
    }
    public long nextLong() throws IOException {
        return Long.parseLong(nextToken());
    }
    public double nextDouble() throws IOException {
        return Double.parseDouble(nextToken());
    }
}