#include <iostream>
#include <algorithm>
using namespace std;
const int N = (1<<17) + 1, K = 131071;
int g[N<<1], Ans[N], Sum[N<<1], Lz[N<<1];
int getLeft(int cr){
cr += K;
if (g[cr] == 1)
return cr - K;
int gcd = g[cr];
while (1){
if (cr & 1){
int gg = __gcd(gcd, g[cr - 1]);
if (gg == 1){
cr--;
break;
}
gcd = gg;
}
cr >>= 1;
}
while (cr <= K){
int gg = __gcd(gcd, g[cr*2+1]);
cr <<= 1;
if (gg == 1)
cr++;
else
gcd = gg;
}
return cr - K;
}
int getRight(int cr){
cr += K;
if (g[cr] == 1)
return cr - K;
int gcd = g[cr];
while (1){
if ((cr & 1) == 0){
int gg = __gcd(gcd, g[cr + 1]);
if (gg == 1){
cr++;
break;
}
gcd = gg;
}
cr >>= 1;
}
while (cr <= K){
int gg = __gcd(gcd, g[cr*2]);
cr <<= 1;
if (gg > 1)
cr++, gcd = gg;
}
return cr - K;
}
void Upd(int cur, int vl, int sz){
Sum[cur] += vl * sz;
Lz[cur] += vl;
}
void Push(int cur, int lc, int rc, int sz){
Upd(lc, Lz[cur], sz);
Upd(rc, Lz[cur], sz);
Lz[cur] = 0;
}
void Add(int l, int r, int v, int cur = 1, int st = 1, int en = N){
if (l >= en or r <= st)
return;
if (l <= st and r >= en){
Upd(cur, v, en - st);
return;
}
int lc = cur + cur, rc = lc + 1, mid = (st + en) / 2;
Push(cur, lc, rc, mid - st);
Add(l, r, v, lc, st, mid);
Add(l, r, v, rc, mid, en);
Sum[cur] = Sum[lc] + Sum[rc];
}
int get(int l, int r, int cur = 1, int st = 1, int en = N){
if (l >= en or r <= st)
return 0;
if (l <= st and r >= en)
return Sum[cur];
int lc = cur + cur, rc = lc + 1, mid = (st + en) / 2;
Push(cur, lc, rc, mid - st);
return get(l, r, lc, st, mid) + get(l, r, rc, mid, en);
}
int main(){
for (int i=1;i<N;i++)
Ans[i] = Ans[i-1] + i;
int n, q;
cin>>n>>q;
g[K + 1] = g[K + n + 2] = 1;
for (int i=2;i<=n+1;i++)
cin>>g[i + K];
for (int i=K;i>=1;i--)
g[i] = __gcd(g[i*2], g[i * 2 + 1]);
for (int i=2;i<=n+1;i++){
int k = getLeft(i);
Add(i, i + 1, i - k);
}
for (int i=1;i<=q;i++){
int t, l, r;
cin>>t>>l>>r, l++;
if (t == 2){
r++;
int R = getRight(l);
if (R > r)
cout<<Ans[r - l + 1]<<'\n';
else
cout<<Ans[R - l] + get(R, r + 1)<<'\n';
continue;
}
int cur = l;
while (cur <= n + 1){
int L = getLeft(cur);
int R = getRight(L + 1);
if (L >= l)
break;
Add(cur, R, L - l);
cur = R;
}
cur = l + K, g[cur] = r;
while (cur > 1)
cur >>= 1, g[cur] = __gcd(g[cur * 2], g[cur * 2 + 1]);
cur = l;
while (cur <= n + 1){
int L = getLeft(cur);
int R = getRight(L + 1);
if (L >= l)
break;
Add(cur, R, l - L);
cur = R;
}
}
}
