#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int M = (2 << 17), N = 1e5+5, K = 29;
int n, q, a[N];
struct node {
ll lazy, sm;
} seg[M];
void push(int v, int s, int e)
{
int lc = 2 * v, rc = lc + 1, mid = (s + e) / 2;
seg[lc].lazy = seg[rc].lazy = seg[v].lazy;
seg[v].lazy = 0;
seg[lc].sm = seg[lc].lazy * (mid - s);
seg[rc].sm = seg[rc].lazy * (e - mid);
}
void SetRange(int l, int r, int val, int s = 0, int e = n, int v = 1)
{
if(r <= s || e <= l) return;
if(l <= s && e <= r)
{
seg[v].lazy = val;
seg[v].sm = seg[v].lazy * (e - s);
return;
}
if(seg[v].lazy)
push(v, s, e);
int mid = (s + e) / 2, lc = 2 * v, rc = lc + 1;
SetRange(l, r, val, s, mid, lc);
SetRange(l, r, val, mid, e, rc);
seg[v].sm = seg[lc].sm + seg[rc].sm;
}
ll get(int l, int r, int s = 0, int e = n, int v = 1)
{
if(r <= s || e <= l) return 0;
if(l <= s && e <= r) return seg[v].sm;
if(seg[v].lazy)
push(v, s, e);
int mid = (s + e) / 2, lc = 2 * v, rc = lc + 1;
return get(l, r, s, mid, lc) + get(l, r, mid, e, rc);
}
int gc[M];
void update(int p, int val, int s = 0, int e = n, int v = 1)
{
if(p < s || e <= p) return;
if(e - s == 1)
{
gc[v] = val;
return;
}
int mid = (s + e) / 2, lc = 2 * v, rc = lc + 1;
update(p, val, s, mid, lc);
update(p, val, mid, e, rc);
gc[v] = gcd(gc[lc], gc[rc]);
}
int GCD(int l, int r, int s = 0, int e = n, int v = 1)
{
if(r <= s || e <= l) return 0;
if(l <= s && e <= r) return gc[v];
int mid = (s + e) / 2, lc = 2 * v, rc = lc + 1;
return gcd(GCD(l, r, s, mid, lc), GCD(l, r, mid, e, rc));
}
ll sm(int x, int y)
{
return (1ll * y * (y - 1)) / 2 - (1ll * x * (x - 1)) / 2;
}
int main()
{
cin >> n >> q;
for(int i = 0; i < n; i ++) {
cin >> a[i];
update(i, a[i]);
}
int j = -1;
for(int i = 0; i < n; i ++)
{
int ans = 0;
for(int j = 20; j >= 0; j--)
{
ans += (1 << j);
if(i + ans > n || GCD(i, i + ans) == 1) ans -= (1 << j);
}
SetRange(i, i + 1, i + ans);
}
while(q--)
{
int t, x, y;
cin >> t >> x >> y;
x--;
if(t == 2)
cout << get(x, y) - sm(x, y) << '\n';
else
{
a[x] = y;
update(x, a[x]);
vector<int> vec;
vector<int> val;
vec.push_back(x);
int g = a[x], pos = x;
while(true)
{
for(int i = 20; i >= 0; i --)
{
int l = pos - (1 << i) + 1;
if(l < 0) continue;
if(GCD(l, x + 1) == g) pos = l;
}
pos--;
if(pos >= 0)
{
vec.push_back(pos);
g = GCD(pos, x + 1);
}
else
break;
}
reverse(vec.begin(), vec.end());
for(int i : vec)
{
int ans = 0;
for(int j = 20; j >= 0; j--)
{
ans += (1 << j);
if(i + ans > n || GCD(i, i + ans) == 1) ans -= (1 << j);
}
val.push_back(i + ans);
}
SetRange(0, vec[0] + 1, val[0]);
for(int i = 1; i < n; i ++)
SetRange(vec[i - 1] + 1, vec[i] + 1, val[i]);
}
}
return 0;
}
