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 CPP):

Solution:
#include <bits/stdc++.h>
inline std::vector<size_t> prime_sieve(const size_t to) {
  std::vector<bool> not_prime(to + 1, false);
  for (size_t i = 2; i < to; i++) {
    if (!not_prime[i]) {
      for (size_t j = 2; i * j <= to; j++) {
        not_prime[i * j] = true;
      }
    }
  }
  std::vector<size_t> ret;
  for (size_t i = 2; i <= to; i++) {
    if (!not_prime[i]) {
      ret.emplace_back(i);
    }
  }
  return ret;
}
template <typename T>
inline std::unordered_set<T> vector_to_set(const std::vector<T>& src) {
  std::unordered_set<T> ret;
  for (const auto& i : src) {
    ret.emplace(i);
  }
  return ret;
}
const auto PRIME_TABLE = prime_sieve(1001);
const auto PRIME_SET = vector_to_set(PRIME_TABLE);
std::unordered_map<uint32_t, uint32_t> d_cache;
inline uint32_t compute_d(const uint32_t v) {
  const auto it = d_cache.find(v);
  if (it != d_cache.end()) {
    return it->second;
  }
  std::vector<uint32_t> nfacts;
  auto t = v;
  for (const auto p : PRIME_TABLE) {
    if (t == 1) {
      break;
    }
    if (PRIME_SET.find(t) != PRIME_SET.end()) {
      nfacts.emplace_back(2);
      break;
    }
    uint32_t r = 0;
    while (t % p == 0) {
      r += 1;
      t = t / p;
    }
    if (r) {
      nfacts.emplace_back(r + 1);
    }
  }
  if (t > PRIME_TABLE[PRIME_TABLE.size() - 1]) {
    nfacts.emplace_back(2);
  }
  uint32_t ret = 1;
  for (const auto f : nfacts) {
    ret *= f;
  }
  d_cache.emplace(v, ret);
  return ret;
}
template <typename T>
struct range_t {
  range_t(T from, T to) : from(from), to(to) {}
  T from, to;
  inline T n_elements() const { return this->to - this->from; }
  inline T only() const { return (from + 1) == to; }
  inline T m() const { return (from + to) / 2; }
  inline range_t<T> split_left() const { return {from, m()}; }
  inline range_t<T> split_right() const { return {m(), to}; }
  template <typename OtherT>
  inline bool contains(const range_t<OtherT>& rhs) const {
    return (this->from <= rhs.from) && (this->to >= rhs.to);
  }
};
using range = range_t<size_t>;
template <typename T1, typename T2>
inline bool intersect(const range_t<T1>& lhs, const range_t<T2>& rhs) {
  return (lhs.from < rhs.to) && (lhs.to > rhs.from);
}
struct segtree {
  size_t size;
  std::vector<uint64_t> data;
  std::vector<bool> future;
  std::vector<uint32_t> ones;
  inline range range() const { return {0, this->size}; }
  inline uint64_t get(const ::range& rrange) {
    return this->get_rec(1, 0, rrange, this->range());
  }
  inline uint64_t get_rec(const size_t idx, const size_t times,
                          const ::range& rrange, const ::range& irange) {
    if (!intersect(irange, rrange)) {
      return 0;
    }
    const auto next_times = times;
    if (irange.only() || rrange.contains(irange)) {
      return this->do_get(idx, next_times, irange);
    } else {
      const auto l = this->get_rec(idx * 2, next_times, rrange,
                                   irange.split_left()),
                 r = this->get_rec(idx * 2 + 1, next_times, rrange,
                                   irange.split_right());
      return l + r;
    }
  }
  inline uint64_t do_get(const size_t idx, const size_t times,
                         const ::range& irange) {
    return this->data[idx];
  }
  inline std::pair<uint64_t, bool> do_replace(const size_t idx,
                                              const size_t times,
                                              const ::range& rrange,
                                              const ::range& irange) {
    const auto next_times = times;
    if (!this->future[idx]) {
      return {this->data[idx], false};
    }
    if (!intersect(irange, rrange)) {
      return {this->do_get(idx, next_times, irange), this->future[idx]};
    }
    uint64_t ret = 0;
    bool has_future = true;
    if (irange.only()) {
      ret = compute_d(this->data[idx]);
      has_future = !((ret == 1) || (ret == 2));
    } else {
      const auto lp = this->do_replace(idx * 2, next_times, rrange,
                                       irange.split_left()),
                 rp = this->do_replace(idx * 2 + 1, next_times, rrange,
                                       irange.split_right());
      ret = lp.first + rp.first;
      has_future = lp.second || rp.second;
    }
    this->data[idx] = ret;
    this->future[idx] = has_future;
    return {ret, has_future};
  }

 private:
  inline std::pair<uint64_t, uint32_t> construct(
      const std::vector<uint64_t>& src, size_t idx, const size_t from,
      const size_t to) {
    if (from + 1 == to) {
      const uint32_t n_one = (src[from] == 1) ? 1 : 0;
      this->data[idx] = src[from];
      this->ones[idx] = n_one;
      return {src[from], n_one};
    }
    const size_t m = (from + to) / 2;
    const auto lp = this->construct(src, idx * 2, from, m);
    const auto rp = this->construct(src, idx * 2 + 1, m, to);
    const uint64_t sum = lp.first + rp.first;
    const auto n_one = lp.second + rp.second;
    this->data[idx] = sum;
    this->ones[idx] = n_one;
    return {sum, n_one};
  }

 public:
  static inline segtree create(const std::vector<uint64_t>& src) {
    const size_t size = std::pow(2, std::ceil(std::log2(src.size())) + 1);
    segtree ret;
    ret.data = std::vector<uint64_t>(size, 0);
    ret.future = std::vector<bool>(size, true);
    ret.ones = std::vector<uint32_t>(size, 0);
    ret.size = src.size();
    ret.construct(src, 1, 0, src.size());
    return ret;
  }
};
int main() {
  std::ios_base::sync_with_stdio(false);
  for (size_t i = 1; i <= 100; i++) {
    compute_d(i);
  }
  size_t n = 0, m = 0;
  std::cin >> n >> m;
  std::vector<uint64_t> data(n, 0);
  for (size_t i = 0; i < n; i++) {
    std::cin >> data[i];
  }
  segtree seg = segtree::create(data);
  for (size_t i = 0; i < m; i++) {
    size_t t = 0, l = 0, r = 0;
    std::cin >> t >> l >> r;
    const range range = {l - 1, r};
    switch (t) {
      case 1:
        seg.do_replace(1, 0, range, seg.range());
        break;
      case 2:
        std::cout << seg.get(range) << '\n';
        break;
      default:
        break;
    }
  }
  return 0;
}