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

public class Main {

    public static int maxSize = 1000001;
    public static int s;
    public static int[] count;
    public static int[] arr;
    public static long[] sumArr;
    public static long[] maxArr;
    public static Reader sc = new Reader();

    public static void build(int n) throws IOException {
        count = new int[maxSize];
        arr = new int[n];
        for(int i = 1; i < maxSize; i++){
            for(int j = i; j < maxSize; j+=i){
                count[j] = count[j] + 1;
            }
        }
        s = 1;
        while(s < n){
            s = s << 1;
        }
        int size = s << 1;
        sumArr = new long[size];
        maxArr = new long[size];
        for(int i = 0; i < n; i++){
            arr[i] = sc.nextInt();
            sumArr[i + s] = arr[i];
            maxArr[i + s] = arr[i];
        }
        for(int i = s - 1; i > 0; i--){
            sumArr[i] = sumArr[i<<1] + sumArr[(i<<1)+1];
            maxArr[i] = Math.max(maxArr[i<<1], maxArr[(i<<1)+1]);
        }
    }

    public static void replace(int arrLeft, int arrRight, int left, int right, int idx){
        if(maxArr[idx] <= 2 || arrRight < left || arrLeft > right) return;
        if(arrLeft == arrRight){
            arr[arrLeft] = count[arr[arrLeft]];
            sumArr[idx] = arr[arrLeft];
            maxArr[idx] = arr[arrLeft];
            return;
        }
        int mid = (arrLeft + arrRight) >> 1;
        replace(arrLeft, mid, left, right, idx << 1);
        replace(mid+1, arrRight, left, right, (idx<<1)+1);
        sumArr[idx] = sumArr[idx<<1] + sumArr[(idx<<1)+1];
        maxArr[idx] = Math.max(maxArr[idx<<1], maxArr[(idx<<1)+1]);
    }

    public static long distinct(int left, int right){
        long sum = 0L;
        for(left+=s, right += s+1; left < right; left = left >> 1, right = right >> 1){
            if((left&1) == 1){
                sum += sumArr[left++];
            }
            if((right&1) == 1){
                sum += sumArr[--right];
            }
        }
        return sum;
    }

    public static void main(String[] args) throws IOException {
        int n = sc.nextInt();
        int q = sc.nextInt();
        build(n);
        for(int i = 0; i < q; i++){
            int command = sc.nextInt();
            int a = sc.nextInt();
            int b = sc.nextInt();
            if(command == 1){
                replace(0, s-1, a-1,b-1, 1);
            }
            else{
                System.out.println(distinct(a-1,b-1));
            }
        }
    }

    public static class Reader
    {
        final private int BUFFER_SIZE = 1 << 16;
        private DataInputStream din;
        private byte[] buffer;
        private int bufferPointer, bytesRead;

        public Reader()
        {
            din = new DataInputStream(System.in);
            buffer = new byte[BUFFER_SIZE];
            bufferPointer = bytesRead = 0;
        }

        public Reader(String file_name) throws IOException
        {
            din = new DataInputStream(new FileInputStream(file_name));
            buffer = new byte[BUFFER_SIZE];
            bufferPointer = bytesRead = 0;
        }

        public String readLine() throws IOException
        {
            byte[] buf = new byte[64]; // line length
            int cnt = 0, c;
            while ((c = read()) != -1)
            {
                if (c == '\n')
                    break;
                buf[cnt++] = (byte) c;
            }
            return new String(buf, 0, cnt);
        }

        public int nextInt() throws IOException
        {
            int ret = 0;
            byte c = read();
            while (c <= ' ')
                c = read();
            boolean neg = (c == '-');
            if (neg)
                c = read();
            do
            {
                ret = ret * 10 + c - '0';
            }  while ((c = read()) >= '0' && c <= '9');

            if (neg)
                return -ret;
            return ret;
        }

        public long nextLong() throws IOException
        {
            long ret = 0;
            byte c = read();
            while (c <= ' ')
                c = read();
            boolean neg = (c == '-');
            if (neg)
                c = read();
            do {
                ret = ret * 10 + c - '0';
            }
            while ((c = read()) >= '0' && c <= '9');
            if (neg)
                return -ret;
            return ret;
        }

        public double nextDouble() throws IOException
        {
            double ret = 0, div = 1;
            byte c = read();
            while (c <= ' ')
                c = read();
            boolean neg = (c == '-');
            if (neg)
                c = read();

            do {
                ret = ret * 10 + c - '0';
            }
            while ((c = read()) >= '0' && c <= '9');

            if (c == '.')
            {
                while ((c = read()) >= '0' && c <= '9')
                {
                    ret += (c - '0') / (div *= 10);
                }
            }

            if (neg)
                return -ret;
            return ret;
        }

        private void fillBuffer() throws IOException
        {
            bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE);
            if (bytesRead == -1)
                buffer[0] = -1;
        }

        private byte read() throws IOException
        {
            if (bufferPointer == bytesRead)
                fillBuffer();
            return buffer[bufferPointer++];
        }

        public void close() throws IOException
        {
            if (din == null)
                return;
            din.close();
        }
    }
}