AC#1#2,Hack

#include<iostream>
#include<cmath>
#include<algorithm>
#define ll long long 
using namespace std;
ll n,m,a[100005],num;
struct node{
	int pre,nxt,val;
}lst[100005];
ll lower(int x) {
	int l=1,r=num+1,mid;
	while(l<r) {
		mid=(l+r)>>1;
		if(lst[mid].val<x) l=mid+1;
		else r=mid;
	} 
	return l;
}
void eraser(int x) {
	lst[lst[x].nxt].pre=lst[x].pre;
	lst[lst[x].pre].nxt=lst[x].nxt;
	lst[x].val=lst[lst[x].pre].val;
}
struct SegmentTree{
	ll l,r,del;
	#define l(x) tr[x].l
	#define r(x) tr[x].r
	#define del(x) tr[x].del
}tr[400005];
void build(int x,int l,int r) {
	l(x)=l,r(x)=r;
	if(l==r) {
		del(x)=a[l];
		return;
	} 
	int mid=(l+r)>>1;
	build(x*2,l,mid),build(x*2+1,mid+1,r);
	del(x)=del(x*2)+del(x*2+1);
}
void update(int x,int l) {
	if(l(x)==r(x)) {
		del(x)=sqrt(a[l]);
		return;
	}
	int mid=(l(x)+r(x))>>1;
	if(l<=mid) update(x*2,l);
	else update(x*2+1,l);
	del(x)=del(x*2)+del(x*2+1); 
}
ll sum(int x,int l,int r) {
	if(l<=l(x)&&r(x)<=r) {
		return del(x);
	}
	int mid=(l(x)+r(x))>>1;
	ll ans=0; 
	if(l<=mid) ans+=sum(x*2,l,r);
	if(r>mid) ans+=sum(x*2+1,l,r);
	return ans;
} 
int main()
{
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=n;i++) if(a[i]!=1) lst[++num].val=i;
	lst[1].pre=0,lst[0].nxt=1,lst[num].nxt=num+1,lst[num+1].pre=num;
	lst[num+1].val=n+1,lst[0].val=n+1;
	for(int i=1;i<=num;i++) lst[i].pre=i-1,lst[i].nxt=i+1;
	build(1,1,n);
	cin>>m;
	while(m--) {
		ll k,l,r;
		cin>>k>>l>>r;
		if(l>r) swap(l,r);
		if(k==0) {
			int k=lower(l);
			for(int i=k;lst[i].val<=r;i=lst[i].nxt) {
				update(1,lst[i].val);
				a[lst[i].val]=sqrt(a[lst[i].val]);
				if(a[lst[i].val]==1) eraser(i);
			}
		} else cout<<sum(1,l,r)<<endl;
	}
	return 0;
}