#include <bits/stdc++.h>
#define sz(c) int(c.size())
#define rep(i,a,b) for (int i=a; i<(b); ++i)
#define per(i,a,b) for (int i=(b)-1; i>=(a); --i)
using namespace std;
using i64 = long long;
using vii = vector<pair<int,int>>;
template<typename Node, int N>
struct segment_tree {
Node tr[2*N];
Node& operator[](int i) {
return tr[i+N];
}
void build() {
per(i,1,N) { tr[i]=merge_nodes(tr[2*i],tr[2*i+1]); }
}
void update(int i) {
i+=N;
for (i/=2; i>0; i/=2) { tr[i]=merge_nodes(tr[2*i],tr[2*i+1]); }
}
void update(int i, const Node &x) {
tr[i]=x;
update(i);
}
Node query(int l, int r) {
Node L,R;
l+=N;
r+=N;
while (l<=r) {
if (l%2==1) { L=merge_nodes(L,tr[l]); }
if (r%2==0) { R=merge_nodes(tr[r],R); }
l=(l+1)/2;
r=(r-1)/2;
}
return merge_nodes(L,R);
}
};
struct node {
i64 count;
vii p,s;
node():count(-1) {}
node(i64 cc, vii pp, vii ss):count(cc),p(pp),s(ss) {}
void set(int x) {
count=(x==1 ? 0 : 1);
p=s={make_pair(x,1)};
}
};
i64 merge_count(const vii &S, const vii &P) {
i64 res=0,r=0,psum=0;
per(l,0,sz(S)) {
while (r<sz(P) && __gcd(S[l].first,P[r].first)>1) {
psum+=P[r].second;
r+=1;
}
res+=S[l].second*psum;
}
return res;
}
vii merge_comb(vii a, const vii &b) {
int cur=a.back().first;
for (const auto &x:b) {
cur=__gcd(cur,x.first);
if (cur==a.back().first) {
a.back().second+=x.second;
} else {
a.emplace_back(cur,x.second);
}
}
return a;
}
node merge_nodes(const node &L, const node &R) {
if (L.count==-1) return R;
if (R.count==-1) return L;
i64 count=L.count+R.count+merge_count(L.s,R.p);
auto p=merge_comb(L.p,R.p);
auto s=merge_comb(R.s,L.s);
return {count,p,s};
}
int const MAXN=110000;
int n,q;
segment_tree<node,MAXN> st;
int main() {
cin.tie(0);
ios_base::sync_with_stdio(0);
cout<<fixed<<setprecision(10);
cin>>n>>q;
rep(i,0,n) {
int x;
cin>>x;
st[i].set(x);
}
st.build();
rep(iq,0,q) {
int t,l,r;
cin>>t>>l>>r;
if (t==1) {
st[l-1].set(r);
st.update(l-1);
} else {
cout<<st.query(l-1,r-1).count<<'\n';
}
}
return 0;
}
