#include <bits/stdc++.h>
#define int long long
#define lc (p << 1)
#define rc (p << 1 | 1)
#define mid ((l + r) >> 1)
using namespace std;
const int N = 1e5 + 5;
int n, m, q, a[N], t[N<<2], t1[N<<2], s[N<<2];
void pushup(int p){
    s[p] = (s[lc] + s[rc]) % m;
}
void add(int p, int l, int r, int x){
    s[p] = (s[p] + (r - l + 1) * x % m) % m; t[p] = (t[p] + x) % m;
}
void mul(int p, int x){
    s[p] = (s[p] * x) % m;
    t[p] = (t[p] * x) % m;
    t1[p] = (t1[p] * x) % m;
}
void pushdown(int p, int l, int r){
    mul(lc, t1[p]), mul(rc, t1[p]);
    add(lc, l, mid, t[p]), add(rc, mid + 1, r, t[p]);
    t[p] = 0, t1[p] = 1;
}
void add(int p, int l, int r, int L, int R, int x){
    if(l > R || r < l) return;
    if(l >= L && r <= R) return add(p, l, r, x);
    pushdown(p, l, r);
    add(lc, l, mid, L, R, x), add(rc, mid + 1, r, L, R, x);
    pushup(p);
}
void mul(int p, int l, int r, int L, int R, int x){
    if(l > R || r < l) return;
    if(l >= L && r <= R) return mul(p, x);
    pushdown(p, l, r);
    mul(lc, l, mid, L, R, x), mul(rc, mid + 1, r, L, R, x);
    pushup(p);
}
void build(int p, int l, int r){
    t1[p] = 1;
    if(l == r) return s[p] = a[l], void();
    build(lc, l, mid), build(rc, mid + 1, r);
    pushup(p);
}
int query(int p, int l, int r, int L, int R){
    if(l > R || r < l) return 0;
    if(l >= L && r <= R) return s[p];
    pushdown(p, l, r);
    return (query(lc, l, mid, L, R) + query(rc, mid + 1, r, L, R)) % m;
}
signed main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
        cin >> a[i];
    build(1, 1, n);
    cin >> q;
    while(q--){
        int op, x, y, k;
        cin >> op >> x >> y;
        if(op == 1){
            cin >> k;
            add(1, 1, n, x, y, k);
        }
        if(op == 2){
            cin >> k;
            mul(1, 1, n, x, y, k);
        }
        if(op == 3)
            cout << query(1, 1, n, x, y) << endl;
    }
    return 0;
}