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.BufferedReader;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.util.TreeSet;

/*
 public class _920F {

 }

 */
public class _920F {
  public class SegmentTree {
    long[] st;
    int n;

    public SegmentTree(int n) {
      st = new long[4 * n];
      this.n = n;
    }

    void build(int i, int[] a, int r1, int r2) {
      if (r1 == r2) {
        st[i] = a[r1];
      } else {
        build(i * 2 + 1, a, r1, (r1 + r2) / 2);
        build(i * 2 + 2, a, (r1 + r2) / 2 + 1, r2);

        st[i] = st[i * 2 + 1] + st[i * 2 + 2];
      }
    }

    long query(int i, int ra, int rb, int r1, int r2) {
      if (ra > r2 || rb < r1) {
        return 0;
      }

      if (ra >= r1 && rb <= r2) {
        return st[i];
      }

      long p1 = query(i * 2 + 1, ra, (ra + rb) / 2, r1, r2);
      long p2 = query(i * 2 + 2, (ra + rb) / 2 + 1, rb, r1, r2);

      return p1 + p2;
    }

    long update(int i, int ra, int rb, int ind, long val) {
      if (ra == rb && rb == ind) {
        st[i] = val;
        return st[i];
      }

      if (ra > ind || rb < ind) {
        return st[i];
      }

      long p1 = update(i * 2 + 1, ra, (ra + rb) / 2, ind, val);
      long p2 = update(i * 2 + 2, (ra + rb) / 2 + 1, rb, ind, val);

      return st[i] = p1 + p2;
    }
  }

  public void solve() throws FileNotFoundException {
    InputStream inputStream = System.in;

    InputHelper in = new InputHelper(inputStream);

    // actual solution
    int n = in.readInteger();

    int m = in.readInteger();

    int[] a = new int[n];

    for (int i = 0; i < n; i++) {
      a[i] = in.readInteger();
    }

    int[] nod = new int[1000001];

    for (int i = 1; i <= 1000000; i++) {
      for (int j = i; j <= 1000000; j += i) {
        nod[j]++;
      }
    }

    TreeSet<Integer> ts = new TreeSet<Integer>();

    for (int i = 0; i < n; i++)
      ts.add(i);

    SegmentTree st = new SegmentTree(n);
    st.build(0, a, 0, n - 1);

    StringBuilder ans = new StringBuilder();
    while (m-- > 0) {
      int t = in.readInteger();
      int l = in.readInteger() - 1;
      int r = in.readInteger() - 1;

      if (t == 1) {
        Integer ni = ts.ceiling(l);

        while (true) {
          if (ni == null || ni > r) {
            break;
          }

          if (a[ni] == 1 || a[ni] == 2) {
            ts.remove(ni);
          } else {
            a[ni] = nod[a[ni]];
            st.update(0, 0, n - 1, ni, a[ni]);
            if (a[ni] == 1 || a[ni] == 2) {
              ts.remove(ni);
            }
          }

          ni = ts.ceiling(ni + 1);
        }
      } else {
        ans.append(st.query(0, 0, n - 1, l, r));
        ans.append("\n");
      }
    }

    System.out.println(ans.toString());
    // end here
  }

  public static void main(String[] args) throws FileNotFoundException {
    (new _920F()).solve();
  }

  class InputHelper {
    StringTokenizer tokenizer = null;
    private BufferedReader bufferedReader;

    public InputHelper(InputStream inputStream) {
      InputStreamReader inputStreamReader = new InputStreamReader(inputStream);
      bufferedReader = new BufferedReader(inputStreamReader, 16384);
    }

    public String read() {
      while (tokenizer == null || !tokenizer.hasMoreTokens()) {
        try {
          String line = bufferedReader.readLine();
          if (line == null) {
            return null;
          }
          tokenizer = new StringTokenizer(line);
        } catch (IOException e) {
          e.printStackTrace();
        }
      }

      return tokenizer.nextToken();
    }

    public Integer readInteger() {
      return Integer.parseInt(read());
    }

    public Long readLong() {
      return Long.parseLong(read());
    }
  }
}