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 _920F {
    static int n, m;
    static long[] a, B;
    static int[] f;
    static TreeSet<Integer> s, pc;
    static void update(int u, long v){
        while(u <= n){
//            out.println(u);
            B[u] += v;
            u += (u & (-u));
        }
    }
    static long get(int u){
        if(u == 0) return 0;
        long res = 0;
        while(u > 0){
            res += B[u];
            u -= u & -u;
        }
        return res;
    }
    static void prime(){
        int N = 1000000;
        f = new int[N + 10];
        for(int i = 2; i * i <= N; i++){
            if(f[i] > 0) continue;
            for(int j = 0; i * i + i * j <= N; j++){
                f[i * i + i * j] = i;
            }
        }
        for(int i = 2; i <= N; i++) if(f[i] == 0) f[i] = i;
    }
    static long calc(long x){
        Map<Integer, Integer> mp = new HashMap<>();
        while(x > 1){
            int nx = f[(int)x];
            if(mp.containsKey((nx)) == false) mp.put(nx, 1);
            else mp.computeIfPresent(nx, (k, v) -> v + 1);
            x /= nx;
        }
        int res = 1;
        for(Map.Entry<Integer, Integer> t : mp.entrySet()){
            res = res * (t.getValue() + 1);
        }
        return res;
    }
    static void run(){
        n = in.nextInt();
        m = in.nextInt();
        a = new long[n + 10];
        B = new long[n + 10];
        s = new TreeSet<>();
        pc = new TreeSet<>();
        for(int i = 1; i <= n; i++){
            a[i] = in.nextInt();
            s.add(i);
            update(i, a[i]);
        }
        prime();
        for(int i = 1; i <= m; i++){
            int t, l, r;
            t = in.nextInt();
            l = in.nextInt();
            r = in.nextInt();
            if(t == 2){
                out.println(get(r) - get(l - 1));
            } else{
                pc = (TreeSet)s.tailSet(l);
                ArrayList<Integer> arl = new ArrayList<>();
                for(int po : pc){
                    if(po > r) break;
                    long newValue = calc(a[(int)po]);
                    update(po, newValue - a[po]);
                    a[po] = newValue;
                    if(newValue <= 2) arl.add(po);
                }
                for(int po : arl){
                    s.remove(po);
                }
            }
        }

    }
    static MyScanner in;
    static PrintWriter out;
    public static void main(String[] args) throws IOException {
        boolean stdStreams = true;
        Locale.setDefault(Locale.US);
        BufferedReader br;
        if (stdStreams) {
            br = new BufferedReader(new InputStreamReader(System.in));
            out = new PrintWriter(System.out);
        } else {
            br = new BufferedReader(new FileReader("C:\\Users\\Admin\\IdeaProjects\\untitled1\\src\\_920F.in"));
            out = new PrintWriter(System.out);
        }
        in = new MyScanner(br);
        int tests = 1;//in.nextInt();
        for (int test = 0; test < tests; test++) {
            new _920F().run();
        }
        br.close();
        out.close();
    }

    static class MyScanner {
        BufferedReader br;
        StringTokenizer st;

        MyScanner(BufferedReader br) {
            this.br = br;
        }

        void findToken() {
            while (st == null || !st.hasMoreTokens()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
        }

        String next() {
            findToken();
            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }

        long nextLong() {
            return Long.parseLong(next());
        }

        double nextDouble() {
            return Double.parseDouble(next());
        }
    }
}