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.*;
 
public class TaskF {
    public static void main(String[] args){
        InputStream  inputstream;
        OutputStream outputstream;
        inputstream = System.in;
        outputstream = System.out;
        InputReader in = new InputReader(inputstream);
        PrintWriter out = new PrintWriter(outputstream);
        Task solver = new Task();
        solver.solve(in,out);
        out.close();
    }
 
    static class Task{
 
        public static final int maxVal = (int)1e6;
        public static final int lg = 8;
        int n,m;
        int[][] d;
        int[] a;
        int[] g = new int[maxVal + 1];
        int[] cntD = new int[maxVal + 1];
        TreeMap <Integer,Integer> tmap = new TreeMap <Integer,Integer> ();
        FenwickTree fen;
 
        public void solve(InputReader in,PrintWriter out){
            n = in.nextInt();
            m = in.nextInt();
            d = new int[n + 1][lg + 1];
            a = new int[n + 1];
            for(int i = 0;i < n;++i){
                a[i] = in.nextInt();
            }
            calc();
            fen = new FenwickTree();
            for(int i = 0;i < n;++i){
                tmap.put(i,0);
                fen.updateNode(i,a[i]);
            }
            for(;m > 0;--m){
                int op,l,r;
                op = in.nextInt();
                l = in.nextInt() - 1;
                r = in.nextInt() - 1;
                if(op == 1){
                    modify(l,r);
                } else {
                    out.println(fen.rsq(l,r));
                }
            }
        }
 
        private void modify(int l,int r){
            while(!tmap.isEmpty() && tmap.ceilingKey(l) != null){
                int f = tmap.ceilingKey(l);
                if(f > r)return;
                int cur = tmap.get(f);
                if(cur < lg - 1){
                    fen.updateNode(f,-d[f][cur]);
                    fen.updateNode(f,+d[f][cur + 1]);
                    tmap.replace(f,cur + 1);
                } else {
                    tmap.remove(f,cur);
                }
                l = f + 1;
            }
        }
 
        private void calc(){
            for(int i = 1;i <= maxVal;++i){
                g[i] = i;
            }
            for(int i = 2;i <= maxVal;++i){
                for(int j = (i << 1);j <= maxVal;j += i){
                    if(g[j] == j){
                        g[j] = i;
                    }
                }
            }
            cntD[1] = 1;
            for(int i = 2;i <= maxVal;++i){
                int tmp = i;
                cntD[i] = 1;
                for(int j = g[tmp];tmp > 1;j = g[tmp]){
                    int c = 0;
                    while(tmp % j == 0){
                        tmp /= j;
                        ++c;
                    }
                    cntD[i] *= (c + 1);
                }
            }
            for(int i = 0;i < n;++i){
                for(int j = 0;j < lg;++j){
                    d[i][j] = (j > 0 ? cntD[d[i][j - 1]] : a[i]);
                }
            }
        }
 
        private class FenwickTree{
            long[] ft;
            FenwickTree(){
                ft = new long[n + 1];
            }
 
            void updateNode(int node,int cur_val){
                for(++node;node <= n;node += node & (-node)){
                    ft[node] += (long)cur_val;
                }
            }
 
            long rsq(int node){
                long ret = 0;
                for(;node > 0;node -= node & (-node)){
                    ret += ft[node];
                }
                return ret;
            }
 
            long rsq(int l,int r){
                return rsq(r + 1) - rsq(l);
            }
        }
    }
 
    static class InputReader{
        public BufferedReader reader;
        public StringTokenizer tokenizer;
 
        public InputReader(InputStream stream){
            reader = new BufferedReader(new InputStreamReader(stream));
            tokenizer = null;
        }
 
        public String next(){
            while(tokenizer == null || !tokenizer.hasMoreTokens()){
                try{
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e){
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }
 
        public int nextInt(){
            return Integer.parseInt(next());
        }
    }
}