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.StringTokenizer;

public class Test {
    static InputReader in;
    static PrintWriter out;
    static int[] divisors;
    public static void main(String[] args) {
        in = new InputReader();
        out = new PrintWriter(System.out);
        int size = (int)1e6;
        divisors = new int[size+1];
        for(int i=1;i<=size;++i){
            int j = i;
            while(j<=size){
                divisors[j]++;
                j+=i;
            }
        }
        int n = in.ni();
        int m = in.ni();
        long[] arr = new long[n];
        for(int i=0;i<n;++i)
            arr[i] = in.ni();
        SegmentTree tree = new SegmentTree(arr,n);
        while(m-->0){
            int type = in.ni();
            int l = in.ni()-1;
            int r = in.ni()-1;
            if(type==1)
                tree.replace(0,n-1,l,r,0);
            else
                out.println(tree.query(0,n-1,l,r,0));
        }
        out.close();
    }

    static class Element{
        long sum;
        boolean allOnesTwos;
        Element(long sum, boolean allOnesTwos) {
            this.sum = sum;
            this.allOnesTwos = allOnesTwos;
        }
    }

    static class SegmentTree{
        Element[] tree;
        long[] check;

        void replace(int start,int end,int qStart,int qEnd,int index){
            if(start>qEnd || end<qStart)
                return;
            if(tree[index].allOnesTwos)
                return;
            if(start==end){
                tree[index].sum = divisors[(int)tree[index].sum];
                if(tree[index].sum<=2)
                    tree[index].allOnesTwos = true;
                else
                    tree[index].allOnesTwos = false;
                return;
            }
            int mid = (start+end)/2;
            replace(start,mid,qStart,qEnd,2*index+1);
            replace(mid+1,end,qStart,qEnd,2*index+2);
            tree[index].sum = tree[2*index+1].sum+tree[2*index+2].sum;
            tree[index].allOnesTwos = tree[2*index+1].allOnesTwos && tree[2*index+2].allOnesTwos;
        }

        long query(int start,int end,int qStart,int qEnd,int index){
            if(qStart<=start && qEnd>=end)
                return tree[index].sum;
            if(start>qEnd || end<qStart)
                return 0;
            int mid = (start+end)/2;
            long first = query(start,mid,qStart,qEnd,2*index+1);
            long sec = query(mid+1,end,qStart,qEnd,2*index+2);
            return first+sec;
        }

        SegmentTree(long[] arr,int n){
            int temp = (int)Math.ceil(Math.log(n)/Math.log(2));
            int sss = 2*(int)Math.pow(2,temp)-1;
            check = new long[n];
            for(int i=0;i<n;++i)
                check[i] = arr[i];
            tree = new Element[sss];
            for(int i=0;i<sss;++i)
                tree[i] = new Element(0,true);
            construct(0,n-1,0);
        }

        void construct(int start,int end,int index){
            if(start>end)
                return;
            if(start==end){
                if(check[start]==1 || check[start]==2){
                    tree[index].allOnesTwos = true;
                }
                else{
                    tree[index].allOnesTwos = false;
                }
                tree[index].sum = check[start];
                return;
            }
            int mid = (start+end)/2;
            construct(start,mid,2*index+1);
            construct(mid+1,end,2*index+2);
            tree[index].sum = tree[2*index+1].sum+tree[2*index+2].sum;
            tree[index].allOnesTwos = tree[2*index+1].allOnesTwos && tree[2*index+2].allOnesTwos;
        }
    }


    static class InputReader{
        BufferedReader br;
        StringTokenizer st;

        public InputReader(){
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String n(){
            while (st == null || !st.hasMoreElements()){
                try{
                    st = new StringTokenizer(br.readLine());
                }
                catch (IOException e){}
            }
            return st.nextToken();
        }

        int ni(){
            return Integer.parseInt(n());
        }

        long nl(){
            return Long.parseLong(n());
        }

        double nd(){
            return Double.parseDouble(n());
        }

        String nli(){
            String str = "";
            try{
                str = br.readLine();
            }
            catch (IOException e){}
            return str;
        }

        int[] nia(int[] arr,int start,int end){
            for(int i=start;i<end;++i)
                arr[i] = ni();
            return arr;
        }
    }
}