#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int M = 2 << 17, N = 1e5+5;
int gc[M], a[N], n, q;
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));
}
int main()
{
int q;
cin >> n >> q;
for(int i = 0; i < n; i ++)
{
cin >> a[i];
update(i, a[i]);
}
while(q--)
{
int t, x, y;
cin >>t >> x >> y;
x--;
if(t == 1)
{
a[x] = y;
update(x, a[x]);
}
else
{
ll fans = 0;;
for(int i = x; i < y; i ++)
{
int ans = 0;
for(int j = 20; j >= 0; j--)
{
ans += (1 << j);
if(i + ans > y || GCD(i, i + ans) == 1)
ans -= (1 << j);
}
fans += ans;
}
cout << fans << endl;
}
}
return 0;
}
