TLE on #2 #9 and #10

Code:

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,a[100005],mod;
struct Tree{
	int l,r,v;
}t[100005<<2];
void pushup(int x){
	t[x].v=(t[x<<1].v+t[x<<1|1].v)%mod;
}
void bt(int x,int l,int r){
	t[x].l=l,t[x].r=r;
	if(l==r){
		t[x].v=a[l];
		return;
	}
	int mid=(l+r)>>1;
	bt(x<<1,l,mid);
	bt(x<<1|1,mid+1,r);
	pushup(x);
}
void upd(bool op,int x,int k,int l,int r){//更新=(op?乘法:加法); 
	if(t[x].l==t[x].r){
		t[x].v=(op?t[x].v*k:t[x].v+k)%mod;
		return;
	}
	int mid=(t[x].l+t[x].r)>>1;
	if(l<=mid)
		upd(op,x<<1,k,l,r);
	if(mid<r)
		upd(op,x<<1|1,k,l,r);
	pushup(x);
}
int query(int x,int l,int r){
	if(l<=t[x].l&&t[x].r<=r)
		return t[x].v;
	int mid=(t[x].l+t[x].r)>>1,reans=0;
	if(l<=mid)
		reans+=query(x<<1,l,r);
	if(mid<r)
		reans+=query(x<<1|1,l,r);
	return reans;
}
signed main(){
	scanf("%lld%lld%lld",&n,&m,&mod);
	for(int i=1;i<=n;i++)
		scanf("%lld",a+i);
	bt(1,1,n);
	for(int i=1,op,x,y,k;i<=m;i++){
		scanf("%lld%lld%lld",&op,&x,&y);
		if(op<3)
			scanf("%lld",&k);
		else
			printf("%lld\n",query(1,x,y)%mod);
		if(op==1)
			upd(1,1,k,x,y);
		else if(op==2)
			upd(0,1,k,x,y);
	}
	return 0;
}