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 Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        TaskE solver = new TaskE();
        solver.solve(1, in, out);
        out.flush();out.close();
    }
        static class TaskE {
         long a[],f[];
         void upd(int id,long val,long max){
          while(id<=max){
           f[id]+=val;id+=id&-id;
          }
         }
         TreeSet<Integer>ts=new TreeSet<>();
         long p[],max=1000001;
         void pre(){
          for(int i=1;i<max;i++){
           for(int j=1;j*i<max;j++)p[i*j]++;
          }
         }
         long q(int id){
          long s=0;
          while(id>0){
           s+=f[id];id-=id&-id;
          }return s;
         }
         public void solve(int testNumber, InputReader in, PrintWriter out) {
             int n=in.nextInt(),m=in.nextInt();
             a=new long[n+1];f=new long[n+1];p=new long[1000001];pre();
             for(int i=1;i<n+1;i++){
              a[i]=in.nextLong();upd(i,a[i],n);ts.add(i);
             }
             while(m-->0){
              int t=in.nextInt(),l=in.nextInt(),r=in.nextInt();
              if(t==1){
               Iterator it=ts.tailSet(l,true).iterator();
               while(it.hasNext()){
                int id=(int)it.next();
                if(id>r)break;
                //if(a[id]<=2)it.remove();
                upd(id,p[(int)a[id]]-a[id],n);
                a[id]=p[(int)a[id]];if(a[id]<=2)it.remove();
               }
              }else{
               out.println(q(r)-q(l-1));
              }
             }
         }
    }
    static class InputReader {
        BufferedReader br;
        StringTokenizer st;
        public InputReader(InputStream stream) {
            br = new BufferedReader(new InputStreamReader(stream));
            st = null;
        }

        String next() {
            while (st == null || !st.hasMoreTokens()) {
                String s = null;
                try {
                    s = br.readLine();
                } catch (IOException e) {
                    e.printStackTrace();
                }
                if (s == null)
                    return null;
                st = new StringTokenizer(s);
            }
            return st.nextToken();
        }

        boolean hasMoreTokens() {
            while (st == null || !st.hasMoreTokens()) {
                String s = null;
                try {
                    s = br.readLine();
                } catch (IOException e) {
                    e.printStackTrace();
                }
                if (s == null)
                    return false;
                st = new StringTokenizer(s);
            }
            return true;
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }
        public long nextLong() {
            return Long.parseLong(next());
        }
        public double nextDouble() {
            return Double.parseDouble(next());
        }
    }
}