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 <img align="middle" class="tex-formula" src="https://espresso.codeforces.com/6afb5e3d414ffbb040c175e23c6627da949add06.png" style="max-width: 100.0%;max-height: 100.0%;"/> replace *a*<sub class="lower-index">*i*</sub> with *D*(*a*<sub class="lower-index">*i*</sub>); 1.  SUM *l* *r* — calculate <img align="middle" class="tex-formula" src="https://espresso.codeforces.com/1e50b9417bb7e50d92d43134922596e938249431.png" style="max-width: 100.0%;max-height: 100.0%;"/>. 
Print the answer for each SUM query.
The first line contains two integers *n* and *m* (1 ≤ *n*, *m* ≤ 3·10<sup class="upper-index">5</sup>) — the number of elements in the array and the number of queries to process, respectively.

The second line contains *n* integers *a*<sub class="lower-index">1</sub>, *a*<sub class="lower-index">2</sub>, ..., *a*<sub class="lower-index">*n*</sub> (1 ≤ *a*<sub class="lower-index">*i*</sub> ≤ 10<sup class="upper-index">6</sup>) — the elements of the array.

Then *m* lines follow, each containing 3 integers *t*<sub class="lower-index">*i*</sub>, *l*<sub class="lower-index">*i*</sub>, *r*<sub class="lower-index">*i*</sub> denoting *i*-th query. If *t*<sub class="lower-index">*i*</sub> = 1, then *i*-th query is REPLACE *l*<sub class="lower-index">*i*</sub> *r*<sub class="lower-index">*i*</sub>, otherwise it's SUM *l*<sub class="lower-index">*i*</sub> *r*<sub class="lower-index">*i*</sub> (1 ≤ *t*<sub class="lower-index">*i*</sub> ≤ 2, 1 ≤ *l*<sub class="lower-index">*i*</sub> ≤ *r*<sub class="lower-index">*i*</sub> ≤ *n*).

There is at least one SUM query.
none
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
30
13
4
22
4 2
1 1 1 3
1 1 4
2 1 4
5
10 2
1 1 1 1 1 1 1 1 1 9
1 1 10
2 1 10
12
4 2
1 1 3 1
1 1 4
2 1 4
5
5 3
1 1 1 1 3
2 1 5
1 1 5
2 1 5
7
6
7 10
1 1 1 1 1 1 1
1 1 7
1 1 7
1 1 7
1 1 7
1 1 7
1 1 7
1 1 7
1 1 7
1 1 7
2 1 7
7
#include <iostream>
#include <set>
#include <vector>
#include <fstream>
#include <algorithm>
#include <map>
#include <iterator>
#include <unordered_map>
#include <stdio.h>
#include <string>
#include <iomanip>

using namespace std;

typedef long long ll;
#define int long long


const int sze = 1 << 19, MV = 1e6 + 10;
int tree[sze << 1], tree_max[sze << 1];
int repl[MV];


int get(int l, int r, int lb, int rb, int ind)
{
	if (l == lb && r == rb)
		return tree[ind];

	int m = (lb + rb) >> 1;
	int first = 0, second = 0;
	
	if (l <= m)
		first = get(l, min(m, r), lb, m, ind << 1);

	if (r > m)
		second = get(max(l, m + 1), r, m + 1, rb, ind << 1 | 1);

	return first + second;
}

void update(int l, int r, int lb, int rb, int ind)
{
	if (tree_max[ind] <= 2)
		return;

	if (lb == rb)
	{
		tree[ind] = repl[tree[ind]];
		tree_max[ind] = tree[ind];
		return;
	}


	int m = (lb + rb) >> 1;

	if (l <= m)
		update(l, min(m, r), lb, m, ind << 1);

	if (r > m)
		update(max(l, m + 1), r, m + 1, rb, ind << 1 | 1);

	tree[ind] = tree[ind << 1] + tree[ind << 1 | 1];
	tree_max[ind] = max(tree[ind << 1], tree[ind << 1 | 1]);
}


int used[MV];


signed main()
{
	int n, m;
	scanf("%lld%lld", &n, &m);
	vector<int> values(n);

	for (int i = 2; i * i < MV; ++i)
	{
		if (used[i])
			continue;

		for (int j = i * i; j < MV; j += i)
			used[j] = i;
	}

	repl[1] = 1;
	for (int i = 2; i < MV; ++i)
	{
		if (!used[i])
			repl[i] = 2;
		else
		{
			int x = i;
			int power = 0;
			while (x%used[i] == 0)
			{
				power++;
				x /= used[i];
			}
			repl[i] = repl[x] * (power + 1);
		}
	}

	for (int i = 0; i < n; ++i)
	{
		scanf("%lld", &tree[i + sze]);
		tree_max[sze + i] = tree[sze + i];
	}

	for (int i = sze - 1; i; --i)
	{
		tree[i] = tree[i << 1] + tree[i << 1 | 1];
		tree_max[i] = max(tree_max[i << 1], tree_max[i << 1 | 1]);
	}

	for (int i = 0; i < m; ++i)
	{
		int t, l, r;
		cin >> t >> l >> r;

		if (t == 1)
			update(l, r, 1, sze, 1);
		else
			printf("%lld\n", get(l, r, 1, sze, 1));
	}

	return 0;
}

