선분 수 폭력

#include
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define ll long long
using namespace std;
const ll inf=1e8;
const int N=2e5;
struct Q{int op,l,r;}q[N];
int num[4],tag[N],n,m,op,l,r;
ll a[N],sum[N];
double sumv[N*20],maxn[N*20],minv[N*20];
bool flag[N*20];
ll read(){
	ll num=0;char ch=getchar();
	while(!isdigit(ch))ch=getchar();
	while(isdigit(ch))num=num*10+ch-'0',ch=getchar();
	return num;
}
void Print(ll x){if(x>9)Print(x/10);putchar(x%10+'0');}
double work(ll a,int b){
	if(b==0)return min(a,inf);
	if(b<0){
		double c=a;
		while(a&&b<0){
			c=sqrt(c),b++;
		}
		return min(c,1.0*inf);
	}
	if(a>=inf)return inf;
	while(b){
		a=a*a,b--;
		if(a>=inf)return inf;
	}return a;
}
void subtask1(){
	rep(i,1,m){
		op=q[i].op,l=q[i].l,r=q[i].r;
		if(op==1) rep(i,l,r)tag[i]++;
		if(op==2) rep(i,l,r)tag[i]--;
		if(op==3){
			double ans=0;
			rep(i,l,r)ans+=work(a[i],tag[i]);
			Print(round(ans)),puts("");
		}
	}
}
void subtask2(){
	rep(i,1,n)a[i]=min(a[i],inf);
	rep(i,1,n)sum[i]=sum[i-1]+a[i];
	rep(i,1,m){
		op=q[i].op,l=q[i].l,r=q[i].r;
		Print(sum[r]-sum[l-1]),puts("");
	}
}
void build3(int o,int L,int R){
	int lc=o<<1,rc=o<<1|1,M=L+R>>1;
	if(L==R){
		maxn[o]=a[L];
		sumv[o]=min(a[L],inf);
		return;
	}
	build3(lc,L,M),build3(rc,M+1,R);
	sumv[o]=sumv[lc]+sumv[rc];
	maxn[o]=max(maxn[lc],maxn[rc]);
}
void update3(int o,int L,int R,int ql,int qr){
	int lc=o<<1,rc=o<<1|1,M=L+R>>1;
	if(flag[o])return;
	if(L==R){
		sumv[o]=sqrt(sumv[o]);
		if(sumv[o]<=1)flag[o]=1;
		return;
	}
	if(ql<=M)update3(lc,L,M,ql,qr);
	if(M>1;
	double ans=0;
	
	if(ql<=L&&R<=qr){
		return sumv[o];
	}
	if(ql<=M) ans+=query3(lc,L,M,ql,qr);
	if(M>1;
	if(L==R){
		//cout<>1;
	if(flag[o])return;
	if(L==R){
		sumv[o]=sumv[o]*sumv[o];
		//if(sumv[o]>=inf)flag[o]=1;
	//	cout<inf)flag[o]=1;
		sumv[o]=min(sumv[o],1.0*inf);
		
		return;
	}
	if(ql<=M)update4(lc,L,M,ql,qr);
	if(M>1;
	ll ans=0;
	
	if(ql<=L&&R<=qr) return sumv[o];
	
	if(ql<=M) ans+=query4(lc,L,M,ql,qr);
	if(M20&&a!=0)return inf;
	
	return fuck[i]*pow(2.0,tmp*1.0)>8? 100000000:pow(a[i],pow(2.0,tmp*1.0));
}
void subtask5(){
	//cout<<1;
	rep(i,1,n)fuck[i]=log10(a[i]);
	rep(i,1,m){
		op=q[i].op,l=q[i].l,r=q[i].r;
		if(op==1) tag[l]++,tag[r+1]--;
		if(op==2) tag[l]--,tag[r+1]++;
		if(op==3){
			long double ans=0;
			ll tmp=0;
			rep(i,1,l-1)tmp+=tag[i];
			//rep(i,1,n)tmp[i]=tag[i]+tmp[i-1];
			rep(i,l,r){
				tmp+=tag[i];
				ans+=cal(i,tmp);
			}
			Print(round(ans)),puts("");
		}
	}
}
int main()
{
	freopen("forever.in","r",stdin);
	freopen("forever.out","w",stdout);
	n=read(),m=read();
	rep(i,1,n)a[i]=read();
	rep(i,1,m)scanf("%d%d%d",&q[i].op,&q[i].l,&q[i].r),num[q[i].op]++;
	if(n<=10000)subtask1();
	else if(num[1]==0&&num[2]==0&&num[3])subtask2();
	else if(num[3]==0&&num[1]&&num[2])return 0;
	else if(num[1]==0&&num[2]&&num[3])subtask3();
	else if(num[2]==0&&num[1]&&num[3])subtask4();
	else if(num[3]<=500) subtask5();
	return 0;
}