#include <bits/stdc++.h>
using namespace std;
#define task "main"
#define no "NO"
#define yes "YES"
#define F first
#define S second
#define vec vector
#define _mp make_pair
#define ii pair<int, int>
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define evoid(val) return void(std::cout << val)
#define FOR(i, a, b) for(int i = (a); i <= (b); ++i)
#define FOD(i, b, a) for(int i = (b); i >= (a); --i)
const int MAX_N = (int)1e5 + 5;
int n, q;
int a[MAX_N], f[MAX_N];
struct GCD_IT {
int tree[4 * MAX_N];
void build(int id, int l, int r) {
if (l == r) {
tree[id] = a[l];
return;
}
int mid = (l + r) >> 1;
build(2 * id, l, mid);
build(2 * id + 1, mid + 1, r);
tree[id] = __gcd(tree[2 * id], tree[2 * id + 1]);
}
void update(int id, int l, int r, int pos) {
if (l == r) {
tree[id] = a[pos];
return;
}
int mid = (l + r) >> 1;
if (pos <= mid) update(2 * id, l, mid, pos);
else update(2 * id + 1, mid + 1, r, pos);
tree[id] = __gcd(tree[2 * id], tree[2 * id + 1]);
}
int get(int id, int l, int r, int u, int v) {
if (r < u || l > v) return 0;
if (l >= u && r <= v) return tree[id];
int mid = (l + r) >> 1;
return __gcd(get(2 * id, l, mid, u, v), get(2 * id + 1, mid + 1, r, u, v));
}
// find maximum position j such that gcd(pos..j) > 1
int walkRight(int id, int l, int r, int pos, int num) {
if (r < pos) return num;
if (l >= pos) {
if (__gcd(tree[id], num) > 1) return __gcd(tree[id], num);
while (l != r) {
int mid = (l + r) >> 1;
if (__gcd(tree[2 * id], num) > 1) {
num = __gcd(tree[2 * id], num);
id = 2 * id + 1;
l = mid + 1;
}
else {
id = 2 * id;
r = mid;
}
}
return -(l - 1);
}
int mid = (l + r) >> 1;
int res = walkRight(2 * id, l, mid, pos, num);
if (res <= 0) return res;
num = __gcd(num, res);
return walkRight(2 * id + 1, mid + 1, r, pos, num);
}
// find the leftmost position j such that gcd(j..pos) == num
int walkLeft(int id, int l, int r, int pos, int num) {
if (l > pos) return -1;
if (r <= pos) {
if (__gcd(tree[id], num) == num) return -1;
while (l != r) {
int mid = (l + r) >> 1;
if (__gcd(tree[2 * id + 1], num) == num) {
id = 2 * id;
r = mid;
}
else {
id = 2 * id + 1;
l = mid + 1;
}
}
return l;
}
int mid = (l + r) >> 1;
int res = walkLeft(2 * id + 1, mid + 1, r, pos, num);
if (res >= 0) return res;
return walkLeft(2 * id, l, mid, pos, num);
}
} gcdTree;
struct IT {
struct NODE {
int val, lazy;
long long sum;
NODE() {
val = sum = 0;
lazy = -1;
}
void apply(int num, int l, int r) {
if (num == -1) return;
val = lazy = num;
sum = 1LL * (r - l + 1) * val;
}
} tree[4 * MAX_N];
NODE combine(NODE A, NODE B) {
NODE res;
res.sum = A.sum + B.sum;
res.val = B.val;
return res;
}
void build(int id, int l, int r) {
if (l == r) {
tree[id].val = tree[id].sum = f[l];
return;
}
int mid = (l + r) >> 1;
build(2 * id, l, mid);
build(2 * id + 1, mid + 1, r);
tree[id] = combine(tree[2 * id], tree[2 * id + 1]);
}
void down(int id, int l, int r) {
int mid = (l + r) >> 1;
tree[2 * id].apply(tree[id].lazy, l, mid);
tree[2 * id + 1].apply(tree[id].lazy, mid + 1, r);
tree[id].lazy = -1;
}
void update(int id, int l, int r, int u, int v, int val) {
if (l > v || r < u) return;
if (l >= u && r <= v) {
tree[id].apply(val, l, r);
return;
}
down(id, l, r);
int mid = (l + r) >> 1;
update(2 * id, l, mid, u, v, val);
update(2 * id + 1, mid + 1, r, u, v, val);
tree[id] = combine(tree[2 * id], tree[2 * id + 1]);
}
long long get(int id, int l, int r, int u, int v) {
if (l > v || r < u) return 0;
if (l >= u && r <= v) return tree[id].sum;
down(id, l, r);
int mid = (l + r) >> 1;
return get(2 * id, l, mid, u, v) + get(2 * id + 1, mid + 1, r, u, v);
}
// find nearest position j such that f[j] >= val
int walk(int id, int l, int r, int val) {
if (l == r) {
if (tree[id].val >= val) return l;
return l + 1;
}
int mid = (l + r) >> 1;
if (tree[2 * id].val >= val) return walk(2 * id, l, mid, val);
return walk(2 * id + 1, mid + 1, r, val);
}
} resTree;
long long getSum(int l, int r) {
if (l > r) return 0;
return 1LL * (r - l + 1) * (r + l) / 2;
}
void solve() {
cin >> n >> q;
FOR(i, 1, n) cin >> a[i];
gcdTree.build(1, 1, n);
FOR(i, 1, n) {
f[i] = gcdTree.walkRight(1, 1, n, i, a[i]);
if (f[i] <= 0) f[i] = -f[i];
else f[i] = n;
}
resTree.build(1, 1, n);
while (q--) {
int type, x, y;
cin >> type >> x >> y;
if (type == 1) {
a[x] = y;
gcdTree.update(1, 1, n, x);
if (y == 1) {
resTree.update(1, 1, n, x, x, x);
int L = resTree.walk(1, 1, n, x);
resTree.update(1, 1, n, L, x, x - 1);
continue;
}
int R = x;
while (R > 0 && gcdTree.get(1, 1, n, R, x) > 1) {
int L = gcdTree.walkLeft(1, 1, n, R, gcdTree.get(1, 1, n, R, x));
if (L < 0) L = 0;
int rightmost = gcdTree.walkRight(1, 1, n, R, a[R]);
if (rightmost <= 0) rightmost = -rightmost;
else rightmost = n;
resTree.update(1, 1, n, L + 1, R, rightmost);
R = L;
}
if (R > 0) {
int L = resTree.walk(1, 1, n, x);
if (L <= R) resTree.update(1, 1, n, L, R, x - 1);
}
}
else {
int pos = max(x, resTree.walk(1, 1, n, y));
cout << resTree.get(1, 1, n, x, pos - 1) - getSum(x - 1, pos - 2) + getSum(1, y - pos + 1) << "\n";
}
}
}
int32_t main() {
if (fopen(task".inp", "r")) {
freopen(task".inp", "r", stdin);
freopen(task".out", "w", stdout);
}
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
bool multitest = 0;
int numTest = 1;
if (multitest) cin >> numTest;
while (numTest--) {
solve();
}
return 0;
}
/* Lak lu theo dieu nhac!!!! */
