RT.thx.

#include<iostream>
#include<cmath>
#define int long long
using namespace std;
int n,m,k,a[200010],l,r,size,pos[200010];
struct BLOCK_T{
	int le,rt,adds,tag;
}block[10010];
int BLOCKSIZE;
int at_block_return(int now){
	return pos[now];
}
bool at_the_same_block(int x,int y){
	return at_block_return(x)==at_block_return(y);
}
int adds=0,blocktot=0;
void addblock(){
	BLOCKSIZE=floor(sqrt(n));
	for(int i=0;i<n;i++){
		adds+=a[i];
		pos[i]=blocktot;
		if(i>=(blocktot+1)*BLOCKSIZE-1){
			block[blocktot].adds=adds;
			block[blocktot].le=blocktot*BLOCKSIZE;
			block[blocktot].rt=min(block[blocktot].le+BLOCKSIZE-1,n-1);
			block[blocktot].tag=0;
//			cout<<blocktot<<' '<<block[blocktot].le<<' '<<block[blocktot].rt<<endl;
//	system("pause");
			adds=0;
			blocktot++;
		}
	}
	block[blocktot].adds=adds;
	block[blocktot].le=blocktot*BLOCKSIZE;
	block[blocktot].rt=min(block[blocktot].le+BLOCKSIZE-1,n-1);
	block[blocktot].tag=0;
//	cout<<blocktot<<' '<<block[blocktot].le<<' '<<block[blocktot].rt<<endl;
}
void add(int le,int rt){
	if(at_the_same_block(le,rt)){
		if(block[at_block_return(rt)].tag<6)
			for(int i=le;i<=rt;i++){
				block[at_block_return(rt)].adds-=a[i];
				a[i]=floor(sqrt(a[i]));
				block[at_block_return(rt)].adds+=a[i];
			}
		block[at_block_return(rt)].tag++;
		return;
	}
	int lblock=at_block_return(le),rblock=at_block_return(rt);
	add(le,block[lblock].rt);
	add(block[rblock].le,rt);
	lblock++;
	for(int i=lblock;i<rblock;i++){
		block[i].tag++;
		if(block[i].tag>=6)block[i].adds=BLOCKSIZE;
		else
			for(int j=block[i].le;j<=block[i].rt;j++){
				block[i].adds-=a[j];
				a[j]=floor(sqrt(a[j]));
				block[i].adds+=a[j];
			}
		block[i].tag++;
	}
}
int sum(int le,int rt){
	int ans=0;
//	cout<<le<<' '<<rt<<' '<<at_the_same_block(le,rt)<<endl;
	if(at_the_same_block(le,rt)){
		for(int i=le;i<=rt;i++)
			ans+=a[i];
		return ans;
	}
	int lblock=at_block_return(le),rblock=at_block_return(rt);
	ans+=sum(le,block[lblock].rt)+sum(block[rblock].le,rt);
	lblock++;
	// cout<<ans<<endl;
	for(int i=lblock;i<rblock;i++)
		ans+=block[i].adds;
	// cout<<le<<' '<<rt<<' '<<ans<<endl;
	return ans;
}
signed main(){
	cin>>n;
	for(int i=0;i<n;i++)cin>>a[i];
	cin>>m;
	addblock();
	for(int i=0;i<m;i++){
		cin>>size;
		cin>>l>>r;
		l--;r--;
		if(l>r)swap(l,r);
		if(!size){
			add(l,r);
			// for(int i=0;i<blocktot;i++)
				// cout<<block[i].adds<<' ';
			// cout<<endl;
		}
		else{
			cout<<sum(l,r)<<endl;
		}
	}
	return 0;
}
/*
10
1 2 3 4 5 6 7 8 9 10
5
0 1 10

1 1 10

1 1 5

0 5 8

1 4 8

*/