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.lang.reflect.Array;
import java.math.*;
import java.text.DecimalFormat;
import java.util.*;




public class Main {
    private static final int MAX = 1000*1000,MAXP2 = 1 << 19,MAXST = MAXP2 << 1;
    private static int n,m;
    private static int [] A;
    private static int [] sig0;
    private static long [] ST = new long[MAXST];
    private static boolean [] finite = new boolean[MAXST];

    private static void init(){
        sig0 = new int[MAX + 1];
        for (int i = 1;i <= MAX;i++)
            for (int j = i;j <= MAX;j += i)
                sig0[j] ++;
    }

    private static void build(int node,int s,int e) {
        if (s == e) {
            ST[node] = A[s];
            finite[node] = A[s] == sig0[A[s]];
            return;
        }
        int m = (s + e) >> 1,left = node*2 + 1,right = left + 1;
        build(left,s,m);
        build(right,m+1,e);
        ST[node] = ST[left] + ST[right];
        finite[node] = finite[left] && finite[right];
    }

    private static void update(int node,int s,int e,int l,int r) {
        if (finite[node]) return;
        if (s == e) {
            A[s] = sig0[A[s]];
            ST[node] = A[s];
            finite[node] = A[s] == sig0[A[s]];
            return;
        }
        int m = (s + e) >> 1,left = node*2 + 1,right = left + 1;
        if (r <= m) update(left,s,m,l,r);
        else if (m < l) update(right,m+1,e,l,r);
        else {
            update(left,s,m,l,m);
            update(right,m+1,e,m+1,r);
        }
        ST[node] = ST[left] + ST[right];
        finite[node] = finite[left] && finite[right];
    }

    private static long query(int node,int s,int e,int l,int r) {
        if (l <= s && e <= r) return ST[node];
        int m = (s + e) >> 1,left = node*2 + 1,right = left + 1;
        if (r <= m) return query(left,s,m,l,r);
        else if (m < l) return query(right,m+1,e,l,r);
        else return query(left,s,m,l,m) + query(right,m+1,e,m+1,r);
    }

    public static void main(String[] args) throws Exception{
        IO io = new IO(null,null);
        init();
        n = io.getNextInt();
        m = io.getNextInt();

        A = new int[n + 1];
        for (int i = 1;i <= n;i++) A[i] = io.getNextInt();

        build(0,1,n);
        while (m-- > 0) {
            int t = io.getNextInt(),l = io.getNextInt(),r = io.getNextInt();
            if (t == 1)  update(0,1,n,l,r);
            else io.println(query(0,1,n,l,r));
        }
        io.close();
    }
}



class IO{
    private BufferedReader br;
    private StringTokenizer st;
    private PrintWriter writer;
    private String inputFile,outputFile;

    public boolean hasMore() throws IOException{
        if(st != null && st.hasMoreTokens()) return true;
        if(br != null && br.ready()) return true;
        return false;
    }
    public String getNext() throws FileNotFoundException, IOException{
        while(st == null || !st.hasMoreTokens()) st = new StringTokenizer(br.readLine());
        return st.nextToken();
    }

    public String getNextLine() throws FileNotFoundException, IOException{
        return br.readLine().trim();
    }

    public int getNextInt() throws FileNotFoundException, IOException{
        return Integer.parseInt(getNext());
    }
    public long getNextLong() throws FileNotFoundException, IOException{
        return Long.parseLong(getNext());
    }

    public void print(double x,int num_digits) throws  IOException{
        writer.printf("%." + num_digits + "f" ,x);
    }
    public void println(double x,int num_digits) throws  IOException{
        writer.printf("%." + num_digits + "f\n" ,x);
    }
    public void print(Object o) throws  IOException{
        writer.print(o.toString());
    }

    public void println(Object o) throws  IOException{
        writer.println(o.toString());
    }
    public IO(String x,String y) throws FileNotFoundException, IOException{
        inputFile = x;
        outputFile = y;
        if(x != null) br = new BufferedReader(new FileReader(inputFile));
        else br = new BufferedReader(new InputStreamReader(System.in));
        if(y != null) writer = new PrintWriter(new BufferedWriter(new FileWriter(outputFile)));
        else writer = new PrintWriter(new OutputStreamWriter(System.out));
    }

    protected void close() throws IOException{
        br.close();
        writer.close();
    }
    public void outputArr(Object [] A) throws IOException{
        int L = A.length;
        for (int i = 0;i < L;i++) {
            if(i > 0) writer.print(" ");
            writer.print(A[i]);
        }
        writer.print("\n");
    }
}