只过了#1 #3 #4

#include<bits/stdc++.h>
#define int long long
using namespace std;
#define lid (id << 1)
#define rid (id << 1 | 1)
using ll = long long;

constexpr int MAXN = 1e6 + 55;
constexpr int root = 1;
int mod;

struct Node{
    int add, sum, mul;
}t[MAXN];

int a[MAXN];

namespace sgt{
    void merge(int id){
        t[id].sum = (t[lid].sum + t[rid].sum) % mod;
        t[id].mul = 1, t[id].add = 0;
    }

    void build(int id, int l , int r){
        if(l == r){
            t[id].sum = a[l];
            t[id].add = 0;
            t[id].mul = 1;
            return ;
        }
        int mid = l + r >> 1;
        build(lid, l, mid);
        build(rid, mid + 1, r);
        merge(id);
    }

    void push_down(int id, int cl, int cr){
        int mid = cl + cr >> 1;
        t[lid].sum = (t[lid].sum * t[id].mul + (mid - cl + 1) * t[id].add) % mod;
        t[rid].sum = (t[rid].sum * t[id].mul + (cr - mid) * t[id].add) % mod;
        t[lid].mul *= t[id].mul;t[lid].mul %= mod;
        t[rid].mul *= t[id].mul;t[rid].mul %= mod;
        t[lid].add += t[id].add;t[lid].add %= mod;
        t[rid].add += t[id].add;t[rid].add %= mod;
        t[id].add = 0, t[id].mul = 1;
    }

    ll qry(int l, int r, int id, int cl, int cr){
        if(r < cl || l > cr)return 0;
        if(cl >= l && cr <= r){
            return t[id].sum;
        }
        push_down(id, cl, cr);
        int mid = cl + cr >> 1;
        return (qry(l, r, lid, cl, mid) + qry(l, r, rid, mid + 1, cr)) % mod;
    }

    void modify_add(int l, int r, ll x, int id, int cl , int cr){
        if(r < cl || l > cr)return ;
        if(cl >= l && cr <= r){
            t[id].add += x;t[id].add %= mod;
            t[id].sum += (cr - cl + 1) * x;t[id].sum %= mod;
            return ;
        }
        int mid = cl + cr >> 1;
        push_down(id, cl, cr);
        modify_add(l, r, x, lid, cl, mid);
        modify_add(l, r, x, rid, mid + 1, cr);
        merge(id);
    }

    void modify_mul(int l, int r, ll x, int id, int cl , int cr){
        if(r < cl || l > cr)return ;
        if(cl >= l && cr <= r){
            t[id].mul *= x;t[id].mul %= mod;
            t[id].sum *= x;t[id].sum %= mod;
            t[id].add *= x;t[id].add %= mod;
            return ;
        }
        int mid = cl + cr >> 1;
        push_down(id, cl, cr);
        modify_mul(l, r, x, lid, cl, mid);
        modify_mul(l, r, x, rid, mid + 1, cr);
        merge(id);
    }
}

signed main(){
    int n, y;
    cin >> n >> y >> mod;
    for(int i = 1; i <= n; i ++){
        cin >> a[i];
    }
    sgt::build(1, 1, n);
    while(y --){
        int flag, a, b, c;
        cin >> flag;
        if(flag == 1){
            cin >> a >> b >> c;
            sgt::modify_mul(a, b, c % mod, root, 1, n);
        } else if(flag == 2){
            cin >> a >> b >> c;
            sgt::modify_add(a, b, c % mod, root, 1, n);    
        } else {
            cin >> a >> b;
            cout << sgt::qry(a, b, root, 1, n) % mod << endl;
        }
    }
}