$题目描述$

$老师交给小可可一个维护数列的任务，现在小可可希望你来帮他完成。$

$有长为n的数列，不妨设为a_1, a_2…a_n。有如下三种操作形式：$

$把数列中的一段数全部乘一个值；$

$把数列中的一段数全部加一个值；$

$询问数列中的一段数的和，由于答案可能很大，你只需输出这个数模P的值。$

$输入格式$

$第一行两个整数n和P$

$第二行含有n个非负整数，从左到右依次为a_1,a_2…a_n；$

$第三行有一个整数m，表示操作总数；$

$从第四行开始每行描述一个操作，输入的操作有以下三种形式：$

$操作1;1, l, r, c，表示把所有满足l<=i<=r的 改为a_i * c；$

$操作2：2, l, r, c ，表示把所有满足1<=i<=r的 改为a_i + c；$

$操作3：3, l, r ，询问所有满足l<=i<=r的a_i之和模P的值。$

$输出格式$

$对每个操作 ，按输入中出现的顺序，依次输出一行一个整数表示询问结果。$

输入样例

7 43
1 2 3 4 5 6 7
5
1 2 5 5
3 2 4
2 3 7 9
3 1 3
3 4 7

输出样例

2
35
8

#include<bits/stdc++.h>
using namespace std;
#define re register 
#define ll long long
const int N = 1e7 + 1;
ll n, m, p, mod, a[N];
struct Tree{
    ll sum;
    ll plue;
    ll mul;
}tree[N];
inline ll read()
{
    char c = getchar();
    ll f = 1,x = 0;
    while(!isdigit(c)){if(c == '-') f = -1; c = getchar();}
    while(isdigit(c)){x = (x << 1) + (x << 3) + (c - '0'); c = getchar();}
    return x * f;
}
inline void pushup(ll k){
    tree[k].sum = tree[k << 1].sum + tree[k << 1 | 1].sum;
    tree[k].sum %= mod;
}
inline void pushdown(ll k, ll l, ll r){
    ll k1 = k << 1;
    ll k2 = k << 1 | 1;
    ll mid = (l + r) >> 1;
    tree[k1].sum *= tree[k].mul; tree[k1].sum %= mod;
    tree[k1].sum += tree[k].plue * (mid - l + 1) % mod; tree[k1].sum %= mod;
    tree[k2].sum *= tree[k].mul; tree[k2].sum %= mod;
    tree[k2].sum += tree[k].plue * (r - mid) % mod; tree[k2].sum %= mod;
    tree[k1].mul *= tree[k].mul; tree[k1].mul %= mod;
    tree[k2].mul *= tree[k].mul; tree[k2].mul %= mod;
    tree[k1].plue *= tree[k].mul; tree[k1].plue %= mod;
    tree[k1].plue += tree[k].plue; tree[k1].plue %= mod;
    tree[k2].plue *= tree[k].mul; tree[k2].plue % mod;
    tree[k2].plue += tree[k].plue; tree[k2].plue %= mod;
    tree[k].plue = 0; tree[k].mul = 1;
}
inline void build(ll k, ll l, ll r){
    tree[k].mul = 1;
    if(l == r){
        tree[k].sum = a[l];
        return ;
    }
    ll mid = (l + r) >> 1;
    build(k << 1, l, mid);
    build(k << 1 | 1, mid + 1, r);
    pushup(k);
}
inline void modify_plue(ll k, ll l, ll r, ll x, ll y, ll z){
    if(y < l || r < x) return ;
    if(x <= l && r <= y) {
        tree[k].plue += z; tree[k].plue %= mod;
        tree[k].sum += z * (r - l + 1) % mod; tree[k].sum %= mod;
        return ;
    }
    ll mid = (l + r) >> 1;
    pushdown(k, l, r);
    modify_plue(k << 1, l, mid, x, y, z);
    modify_plue(k << 1 | 1, mid + 1, r, x, y, z);
    pushup(k);
}
inline void modify_mul(ll k, ll l, ll r, ll x, ll y, ll z){
    if(y < l || r < x) return ;
    if(x <= l && r <= y){
        tree[k].sum *= z; tree[k].sum %= mod;
        tree[k].mul *= z; tree[k].mul %= mod;
        tree[k].plue *= z; tree[k].plue %= mod;
        return ;
    }
    ll mid = (l + r) >> 1;
    pushdown(k, l, r);
    modify_mul(k << 1, l, mid, x, y, z);
    modify_mul(k << 1 | 1, mid + 1, r, x, y, z);
    pushup(k);
}
inline ll tree_query(ll k, ll l, ll r, ll x, ll y){
    if(y < l || r < x){
        return 0;
    }
    if(x <= l && r <= y) return tree[k].sum;
    ll mid = (l + r) >> 1;
    pushdown(k, l, r);
    ll s1, s2;
    s1 = tree_query(k << 1, l, mid, x, y);
    s2 = tree_query(k << 1 | 1, mid + 1, r, x, y);
    return (s1 + s2) % mod;
}
int main(){
    n = read(), mod = read();
    for(int i = 1;i <= n;i ++) a[i] = read();
    build(1, 1, n);
    m = read();
    while(m --){
        ll op;
        op = read();
        if(op == 1){
            ll l, r, c;
            l = read(), r = read(), c = read();
            modify_mul(1, 1, n, l ,r, c);
        }
        else if(op == 2){
            ll l, r, c;
            l = read(), r = read(), c = read();
            modify_plue(1, 1, n, l, r, c);
        }
        else if(op == 3){
            ll l, r;
            l = read(), r = read();
            printf("%lld\n", tree_query(1, 1, n, l, r));
        }
    }
    return 0;
}