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.*;
public class F {
        String INPUT = "7 6\n" +
                "6 4 1 10 3 2 4\n" +
                "2 1 7\n" +
                "2 4 5\n" +
                "1 3 5\n" +
                "2 4 4\n" +
                "1 5 7\n" +
                "2 1 7";
        int N = 1000005;
        int[] d = new int[N];
        Pair[] t = new Pair[4*N];
        int[] a = new int[N];
        void solve()
        {
                preprocess();
                int n = i(),q = i();
                for (int i = 1; i <=n ; i++) {
                        a[i] = i();
                }
                build(1,1,n);
                while(q-->0)
                {
                        int type = i(), l = i(), r= i();
                        if(type==2)
                        {
                                out.println(query(1,1,n,l,r));
                        }
                        else
                        {
                                update(1,1,n,l,r);
                        }
                }

        }
        void build(int n,int s,int e)
        {
                if(s==e)
                {
                        t[n] = new Pair(a[s],a[s]==1?1:0);
                        return;
                }
                int m = (s+e)>>1;
                build(2*n,s,m);
                build(2*n+1,m+1,e);
                t[n] = new Pair(t[2*n].a+t[2*n+1].a,0);
        }
        void update(int n,int s,int e,int l,int r)
        {
                if(l>e || r<s)
                        return;
                  if(e-s+1 == t[n].b)
                        return;  
                if(s == e)
                {
                        int x = d[(int)t[n].a];
                        if(x == 2)
                                t[n].b = 1;
                        t[n].a = x;
                        return;
                }
                
                int m = (s+e)>>1;
                update(2*n,s,m,l,r);
                update(2*n+1,m+1,e,l,r);
                t[n].a = t[2*n].a + t[2*n+1].a;
                t[n].b = t[2*n].b + t[2*n+1].b;

        }
        long query(int n,int s,int e,int l,int r)
        {
                if(l>e || r<s)
                        return 0;
                if(l<=s && r>=e)
                        return t[n].a;
                int m = (s+e)>>1;
                long p = query(2*n,s,m,l,r);
                long q = query(2*n+1,m+1,e,l,r);
                return p+q;
        }
        static class Pair{
                long a,b;
                Pair(long a,long b){this.a = a; this.b = b;}
        }
        private void preprocess() {
                d[1] = 1;
                for (int i = 2; i <N ; i++) {
                        d[i]++;
                        for (int j = i; j<N ; j+=i)
                                d[j]++;
                }
        }

        void run() throws Exception{
                is = oj ? System.in: new ByteArrayInputStream(INPUT.getBytes());
                //is = System.in;
                out = new PrintWriter(System.out);
                long s = System.currentTimeMillis();
                solve();
                out.flush();
                tr(System.currentTimeMillis()-s+"ms");
        }
        public static void main(String[] args)throws Exception {
                new F().run();
        }
        InputStream is;
        PrintWriter out;
        private byte[] inbuf = new byte[1024];
        public int lenbuf = 0, ptrbuf = 0;

        private int readByte()
        {
                if(lenbuf == -1)throw new InputMismatchException();
                if(ptrbuf >= lenbuf){
                        ptrbuf = 0;
                        try { lenbuf = is.read(inbuf); } catch (IOException e) { throw new InputMismatchException(); }
                        if(lenbuf <= 0)return -1;
                }
                return inbuf[ptrbuf++];
        }

        private boolean isSpaceChar(int c) { return !(c >= 33 && c <= 126); }
        private int skip() { int b; while((b = readByte()) != -1 && isSpaceChar(b)); return b; }

        private double d() { return Double.parseDouble(s()); }
        private char c() { return (char)skip(); }

        private String s()
        {
                int b = skip();
                StringBuilder sb = new StringBuilder();
                while(!(isSpaceChar(b))){ // when nextLine, (isSpaceChar(b) && b != ' ')
                        sb.appendCodePoint(b);
                        b = readByte();
                }
                return sb.toString();
        }

        private char[] sa(int n)
        {
                char[] buf = new char[n];
                int b = skip(), p = 0;
                while(p < n && !(isSpaceChar(b))){
                        buf[p++] = (char)b;
                        b = readByte();
                }
                return n == p ? buf : Arrays.copyOf(buf, p);
        }

        private char[][] nm(int n, int m)
        {
                char[][] map = new char[n][];
                for(int i = 0;i < n;i++)map[i] = sa(m);
                return map;
        }

        private int[] ia(int n)
        {
                int[] a = new int[n];
                for(int i = 0;i < n;i++)a[i] = i();
                return a;
        }

        private int i()
        {
                int num = 0, b;
                boolean minus = false;
                while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
                if(b == '-'){
                        minus = true;
                        b = readByte();
                }

                while(true){
                        if(b >= '0' && b <= '9'){
                                num = num * 10 + (b - '0');
                        }else{
                                return minus ? -num : num;
                        }
                        b = readByte();
                }
        }

        private long l()
        {
                long num = 0;
                int b;
                boolean minus = false;
                while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
                if(b == '-'){
                        minus = true;
                        b = readByte();
                }

                while(true){
                        if(b >= '0' && b <= '9'){
                                num = num * 10 + (b - '0');
                        }else{
                                return minus ? -num : num;
                        }
                        b = readByte();
                }
        }

        private boolean oj = System.getProperty("ONLINE_JUDGE") != null;
        private void tr(Object... o) { if(!oj)System.out.println(Arrays.deepToString(o)); }

}