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.util.*;
import java.io.*;
import static java.lang.System.in;

public class Main {
    static int n,n0=2,m;
    static int[] dat, dic,a;
    static long[] sum;
    // static ArrayList<Integer>[] graph,tree;
    public static void main(String[] args)throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(in));
        //Scanner sc = new Scanner(System.in);
        String[] buf = reader.readLine().split(" ");
        n = Integer.parseInt(buf[0]); m = Integer.parseInt(buf[1]);
        buf = reader.readLine().split(" ");
        a = new int[n];
        for(int i=0;i<n;i++) a[i]=Integer.parseInt(buf[i]);
        ini(a);
        PrintWriter out = new PrintWriter(System.out);
        for(int pass=0;pass<m;pass++){
            buf = reader.readLine().split(" ");
            int t = Integer.parseInt(buf[0]);
            int a = Integer.parseInt(buf[1])-1,b = Integer.parseInt(buf[2]);
            if(t==1) update(0,a,b,0,n0);
            else {
                long ans = query(0,a,b,0,n0);
                out.println(ans);
            }
        }
        out.flush();
    }
    static void ini(int[] a){
        while(n0<n) n0*=2;
        dat = new int[2*n0-1]; sum = new long[2*n0-1]; // dat[] used to record the max value
        int maxa = 1;
        for(int w:a) maxa = Math.max(maxa,w);
        dic = new int[maxa+1];
        Arrays.fill(dic,1);
        for(int i=2;i<=maxa;i++){
            for(int j=i;j<=maxa;j+=i) dic[j]++;
        }
        for(int i=0;i<n;i++){
            int idx = i+n0-1;
            sum[idx] = a[i]; dat[idx] = a[i];
            while(idx>0){
                idx = (idx-1)/2;
                dat[idx] = Math.max(dat[idx*2+1],dat[idx*2+2]);
            }
        }
        int start = n0;
        while(start>0){
            start = (start-1)/2;
            for(int j=start;j<=2*start;j++) sum[j] = sum[j*2+1]+sum[j*2+2];
        }
    }
    static long query(int k, int a, int b, int le, int ri){
        if(b<=le||ri<=a) return 0;
        if(a<=le&&ri<=b) return sum[k];
        long left = query(k*2+1,a,b,le,(le+ri)>>1);
        long right = query(k*2+2,a,b,(le+ri)>>1,ri);
        return left+right;
    }
    static void update(int k, int a, int b, int le, int ri){
        if(dat[k]<=2||le>=ri) return;
        if(ri<=a||b<=le) return;
        if(le+1==ri){ // single-point update
            int cur = dat[k];
            dat[k] = dic[cur];
            sum[k] = dic[cur];
            return;
        }
        int mid = (le+ri)>>1;
        update(k*2+1,a,b,le,mid);
        update(k*2+2,a,b,mid,ri);
        sum[k] = sum[2*k+1]+sum[2*k+2];
        dat[k] = Math.max(dat[2*k+1],dat[2*k+2]);
    }
}