#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
int const N=1e5+10;
int gc[4*N]={};
int n,q;
struct node
{
int mn=1e9,mx=0;
ll sm=0;
int lazy=-1;
};
node seg[4*N]={};
node merge(node a,node b)
{
node c;
c.sm=a.sm+b.sm;
c.mn=min(a.mn,b.mn);
c.mx=max(a.mx,b.mx);
c.lazy=-1;
return c;
}
void update(int r,int vl,int i=1,int st=0,int en=n-1)
{
if (st==en)
{
gc[i]=vl;return;
}
int mid=(st+en)/2;
if (r<=mid)
update(r,vl,i*2,st,mid);
else
update(r,vl,i*2+1,mid+1,en);
gc[i]=gcd(gc[i*2],gc[i*2+1]);
}
int get(int l,int r,int i=1,int st=0,int en=n-1)
{
if (st>=l&&en<=r)
return gc[i];
if (st>r||en<l)
return 0;
int mid=(st+en)/2;
return gcd(get(l,r,i*2,st,mid),get(l,r,i*2+1,mid+1,en));
}
void push(int i,int st,int en)
{
int mid=(st+en)/2;
int lc=i*2,rc=lc+1;
int vl=seg[i].lazy;
seg[lc].lazy=seg[i].lazy;
seg[lc].mn=seg[lc].mx=vl;
seg[lc].sm=vl*(mid-st+1);
seg[rc].lazy=seg[i].lazy;
seg[rc].mn=seg[rc].mx=vl;
seg[rc].sm=vl*(en-mid);
seg[i].lazy=-1;
}
void upd(int l,int r,int vl,int i=1,int st=0,int en=n-1)
{
if (l>r)
return ;
if (st>=l&&en<=r)
{
seg[i].lazy=vl;
seg[i].mn=seg[i].mx=vl;
seg[i].sm=vl*(en-st+1);
return;
}
if (st>r||en<l)
return;
if (seg[i].lazy!=-1)
push(i,st,en);
int mid=(st+en)/2;
upd(l,r,vl,i*2,st,mid);upd(l,r,vl,i*2+1,mid+1,en);
seg[i]=merge(seg[i*2],seg[i*2+1]);
}
node dm;
node get1(int l,int r,int i=1,int st=0,int en=n-1)
{
if (st>=l&&en<=r)
return seg[i];
if (st>r||en<l)
return dm;
int mid=(st+en)/2;
if (seg[i].lazy!=-1)
push(i,st,en);
return merge(get1(l,r,i*2,st,mid),get1(l,r,i*2+1,mid+1,en));
}
ll f(ll x)
{
return (x*(x+1))/2;
}
ll gd(ll l,ll r)
{
return f(r)-f(l-1);
}
inline void solve()
{
cin>>n>>q;
int a[n];
for (auto& i:a)
cin>>i;
for (int i=0;i<n;i++)
update(i,a[i]);
for (int i=0;i<n;i++)
{
int st=i,en=n;
while (st+1<en)
{
int mid=(st+en)/2;
if (get(i,mid)>1)
st=mid;
else
en=mid;
}
if (a[i]==1)
st=i-1;
upd(i,i,st);
}
while (q--)
{
int ty;
cin>>ty;
if (ty==1)
{
int i,v;
cin>>i>>v;
i--;
update(i,v);
int j=i;
int gc=0;
while (j>=0)
{
gc=get(j,i);
if (gc==1)
break;
int st=-1,en=j;
while (st+1<en)
{
int mid=(st+en)/2;
if (get(mid,j)==gc)
en=mid;
else
st=mid;
}
int ind=en;
st=ind,en=n;
while (st+1<en)
{
int mid=(st+en)/2;
if (get(ind,mid)>1)
st=mid;
else
en=mid;
}
upd(ind,j,st);
j=ind-1;
}
int st=-1,en=j;
while (st+1<en)
{
int mid=(st+en)/2;
if (get1(mid,j).mn>=i)
en=mid;
else
st=mid;
}
upd(en,j,i-1);
}
else
{
int l,r;
cin>>l>>r;
l--;r--;
int st=l-1,en=r+1;
while (st+1<en)
{
int mid=(st+en)/2;
if (get1(mid,r).mn>r)
en=mid;
else
st=mid;
}
ll f=get1(l,st).sm;
f+=1ll*(r-en+1)*(r);
f-=gd(l,r);
f+=(r-l+1);
cout<<f<<endl;
}
}
}
signed main()
{
ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
int t=1;
for (int i=1;i<=t;i++)
{
solve();
}
}
