70pts,WA on #2 #9 #10

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+1;
struct Node{
	ll l;
	ll r;
	ll k;
	ll add;
	ll mul;
}tree[N*4];
ll n,m,Mod,pos;
inline ll build_tree(ll value,ll l,ll r){
	tree[value]=Node{l,r,0,0,1};
	if (l==r){
		ll num;
		scanf("%lld",&num);
		return tree[value].k=num%Mod;
	}
	ll mid=(l+r)>>1;
	return tree[value].k=(build_tree(value*2,l,mid)+build_tree(value*2+1,mid+1,r))%Mod;
}
inline void pushdown(ll value){
	tree[value*2].add=(tree[value].add+tree[value*2].add*tree[value].mul)%Mod;
	tree[value*2+1].add=(tree[value].add+tree[value*2+1].add*tree[value].mul)%Mod;
	tree[value*2].mul=(tree[value].mul*tree[value*2].mul)%Mod;
	tree[value*2+1].mul=(tree[value].mul*tree[value*2+1].mul)%Mod;
	tree[value*2].k=(tree[value].mul*tree[value*2].k+tree[value].add*(tree[value*2].r-tree[value*2].l+1))%Mod;
	tree[value*2+1].k=(tree[value].mul*tree[value*2+1].k+tree[value].add*(tree[value*2+1].r-tree[value*2+1].l+1))%Mod;
	tree[value].add=0;
	tree[value].mul=1;
}
inline ll query(ll value,ll L,ll R){
	pushdown(value);
	if (tree[value].l>=L&&tree[value].r<=R)
		return tree[value].k%Mod;
	ll mid=(tree[value].l+tree[value].r)>>1;
    return ((L<=mid?query(value*2,L,R):0)+(R>mid?query(value*2+1,L,R):0))%Mod;
}
inline void updata(ll value,ll x,ll pos,ll L,ll R){
	pushdown(value);
	if (pos==1&&tree[value].l>=L&&tree[value].r<=R){
		tree[value].mul=(tree[value].mul*x)%Mod;
        tree[value].add=(tree[value].add*x)%Mod;
        tree[value].k=(tree[value].k*tree[value].mul)%Mod;
        return;
	}
	if(pos==2&&tree[value].l>=L&&tree[value].r<=R){
        tree[value].add=(tree[value].add+x)%Mod;
        tree[value].k=(tree[value].k+tree[value].add*(tree[value].r-tree[value].l+1))%Mod;
        return;
    }
    ll mid=(tree[value].l+tree[value].r)/2;
    if(L<=mid)
        updata(value*2,x,pos,L,R);
    if(R>mid)
        updata((value*2)+1,x,pos,L,R);
    tree[value].k=tree[value*2].k+tree[value*2+1].k;
}
int main(){
	scanf("%lld%lld",&n,&Mod);
	build_tree(1,1,n);
	cin>>m;
	for (ll i=1;i<=m;i++){
		cin>>pos;
		ll x,y;
		cin>>x>>y; 
		if (pos!=3){
			ll k;
			cin>>k;
			updata(1,k,pos,x,y);
		}
		else if (pos==3)
			printf("%lld\n",query(1,x,y));
	}
}