#include<bits/stdc++.h> using namespace std; #define ll long long const int maxn=1e5+5; ll n,m,N,l,r,c,op,ans,s[maxn],pos[maxn],sum[maxn]; bool vis[maxn]; void check_sqrt(int p){ if(vis[p]>0)return; vis[p]=1; sum[p]=0; for(int i=(p-1)*m+1;i<=p*m;i++){ s[i]=sqrt(s[i]); sum[p]+=s[i]; if(s[i]>1)vis[p]=0; } } void change(ll l,ll r,ll c){ if(!vis[pos[l]]){ for(ll i=l;i<=min(pos[l]*m,r);i++){ sum[pos[i]]-=s[i]; s[i]=sqrt(s[i]); sum[pos[i]]+=s[i]; } vis[pos[l]]=1; for(ll i=(pos[l]-1)*m+1;i<=pos[l]*m;i++) if(s[i]>1){ vis[pos[l]]=0; break; } } if(pos[l]!=pos[r]&&vis[pos[r]]==0){ for(ll i=(pos[r]-1)*m+1;i<=r;i++){ sum[pos[i]]-=s[i]; s[i]=sqrt(s[i]); sum[pos[i]]+=s[i]; } vis[pos[r]]=1; for(ll i=(pos[r]-1)*m+1;i<=pos[r]*m;i++){ if(s[i]>1){ vis[pos[r]]=0; break; } } } for(ll i=pos[l]+1;i<=pos[r]-1;i++) check_sqrt(i); } void getsum(ll l,ll r){ ans=0; for(ll i=l;i<=min(pos[l]*m,r);i++)ans+=s[i]; if(pos[l]!=pos[r]){ for(ll i=(pos[r]-1)*m+1;i<=r;i++)ans+=s[i]; } for(ll i=pos[l]+1;i<=pos[r]-1;i++)ans+=sum[i]; printf("%lld\n",ans); } int main(){ scanf("%lld",&n); m=sqrt(n); for(int i=1;i<=n;i++)scanf("%lld",&s[i]); cin>>N; for(int i=1;i<=n;i++)pos[i]=(i-1)/m+1; for(int i=1;i<=n;i++)sum[pos[i]]+=s[i]; for(int i=1;i<=N;i++){ scanf("%lld%lld%lld",&op,&l,&r); if(l>r)swap(l,r); if(op==0)change(l,r,c); else if(op==1)getsum(l,r); } return 0; }