测试小数据似乎也没啥问题，主要是pushdown的时候只更新了当前节点的sum

#include <iostream>

#define int long long

using namespace std;

const int N = 1e5 + 10;

struct Node {
    int l, r, k, b, sum;
}node[N * 4];
int n, p, m;
int a[N];

void pushup(int u) {
    node[u].sum = (node[u << 1].sum + node[u << 1 | 1].sum) % p;
}

void pushdown(int u) {
    node[u].sum = (node[u].sum * node[u].k % p + node[u].b * (node[u].r - node[u].l + 1) % p) % p;
    if (node[u].l != node[u].r) {
        node[u << 1].k = (node[u << 1].k * node[u].k) % p;
        node[u << 1].b = (node[u << 1].b * node[u].k % p + node[u].b) % p;
        node[u << 1 | 1].k = (node[u << 1 | 1].k * node[u].k) % p;
        node[u << 1 | 1].b = (node[u << 1 | 1].b * node[u].k % p + node[u].b) % p;
    }
    node[u].k = 1, node[u].b = 0;
}

void build(int u, int l, int r) {
    node[u] = {l, r, 1, 0, 0};
    if (l == r) {
        node[u].sum = a[l] % p;
        return;
    }
    int mid = l + r >> 1;
    build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
    pushup(u);
}

void add(int u, int l, int r, int c) {
    if (node[u].l >= l && node[u].r <= r) {
        node[u].b = (node[u].b + c) % p;
        pushdown(u);
        return;
    }
    pushdown(u);
    int mid = node[u].l + node[u].r >> 1;
    if (mid >= l) add(u << 1, l, r, c);
    if (mid < r) add(u << 1 | 1, l, r, c);
    pushup(u);
}

void multiply(int u, int l, int r, int c) {
    if (node[u].l >= l && node[u].r <= r) {
        node[u].k = (node[u].k * c) % p;
        node[u].b = (node[u].b * c) % p;
        pushdown(u);
        return;
    }
    pushdown(u);
    int mid = node[u].l + node[u].r >> 1;
    if (mid >= l) multiply(u << 1, l, r, c);
    if (mid < r) multiply(u << 1 | 1, l, r, c);
    pushup(u);
}

int query(int u, int l, int r) {
    int res = 0;
    if (node[u].l >= l && node[u].r <= r) {
        pushdown(u);
        return node[u].sum % p;
    }
    pushdown(u);
    int mid = node[u].l + node[u].r >> 1;
    if (mid >= l) res = (res + query(u << 1, l, r)) % p;
    if (mid < r) res = (res + query(u << 1 | 1, l, r)) % p;
    return res;
}

signed main() {
    scanf("%lld%lld", &n, &p);
    for (int i = 1; i <= n; i ++) {
        scanf("%lld", &a[i]);
    }
    scanf("%lld", &m);
    build(1, 1, n);
    while (m --) {
        int op;
        int t, g, c;
        scanf("%lld", &op);
        if (op == 1) {
            scanf("%lld%lld%lld", &t, &g, &c);
            multiply(1, t, g, c);
        }
        else if (op == 2) {
            scanf("%lld%lld%lld", &t, &g, &c);
            add(1, t, g, c);
        }
        else {
            scanf("%lld%lld", &t, &g);
            printf("%lld\n", query(1, t, g) % p);
        }
    }
    return 0;
}