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 MainClass
{
    static int[] div;
    public static void main(String[] args) throws IOException
    {
        Reader in = new Reader();
        int n = in.nextInt();
        int m = in.nextInt();
        div = new int[1000000 + 5];
        Arrays.fill(div, 1);
        for (int i=2;i<div.length;i++) for (int j=i;j<div.length;j+=i) if (j % i == 0) div[j]++;
        StringBuilder stringBuilder = new StringBuilder();
        int[] A = new int[n];
        BIT BIT = new BIT(n + 10);
        for (int i=0;i<n;i++)
        {
            A[i] = in.nextInt();
            BIT.update(i + 1, A[i]);
        }
        TreeSet<Integer> h = new TreeSet<>();
        for (int i=0;i<n;i++)
        {
            if (A[i] > 2)   h.add(i);
        }
        while (m -- > 0)
        {
            int type = in.nextInt();
            int l = in.nextInt() - 1;
            int r = in.nextInt() - 1;
            if (type == 1)
            {
                int ff = l - 1;
                while (h.higher(ff) != null && h.higher(ff) <= r)
                {
                    ff = h.higher(ff);
                    int oldValue = A[ff];
                    BIT.update(ff + 1, -oldValue);
                    int newValue = findDiv(oldValue, 1);
                    A[ff] = newValue;
                    BIT.update(ff + 1, newValue);
                    if (newValue <= 2)
                        h.remove(ff);
                }
            }
            else
            {
                long sum = BIT.sum(r + 1) - BIT.sum(l);
                stringBuilder.append(sum).append("\n");
            }
        }
        System.out.println(stringBuilder);
    }
    public static int findDiv(int n, int times)
    {
        int count = 0;
        while (count < times)
        {
            if (div[n] == n)
                break;
            else
            {
                n = div[n];
                count++;
            }
        }
        return n;
    }
}
class BIT
{
    int size;
    long[] table;
    public BIT(int size)
    {
        table = new long[size];
        this.size = size;
    }

    void update(int i, long delta)
    {
        while (i < size)
        {
            table[i] += delta;
            i += Integer.lowestOneBit(i);
        }
    }

    long sum(int i)
    {
        long sum = 0L;
        while (i > 0)
        {
            sum += table[i];
            i -= Integer.lowestOneBit(i);
        }
        return sum;
    }
}
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();
    }
}