#include<bits/stdc++.h>

using namespace std;

#define MAXN 500000

typedef long long LL;

struct SegTreeNode {

    LL l,r,sum,lazya,lazyb;

}tree[MAXN+];

LL i,N,P,Q,l,r,x,opt;

LL a[MAXN+];

template <typename T> void read(T &x) {

    LL f=; char c = getchar(); x=;

    for (; !isdigit(c); c = getchar()) { if (c=='-') f=-; }

    for (; isdigit(c); c = getchar()) x=x*+c-'';

    x*=f;

}

inline void write(LL x) {

    if (x < ) {

        putchar('-');

        x = -x;

    }

    if (x /  > ) write(x/);

    putchar(x%+'');

} 

inline void pushup(LL index) {

    tree[index].sum = (tree[index*].sum + tree[index*+].sum) % P;

}

inline void pushdown(LL index) {

    tree[index*].sum = (tree[index*].sum * tree[index].lazya + tree[index].lazyb * (tree[index*].r - tree[index*].l + )) % P;

    tree[index*+].sum = (tree[index*+].sum * tree[index].lazya + tree[index].lazyb * (tree[index*+].r - tree[index*+].l + )) % P;

    tree[index*].lazya = (tree[index*].lazya * tree[index].lazya) % P;

    tree[index*+].lazya = (tree[index*+].lazya * tree[index].lazya) % P;

    tree[index*].lazyb = (tree[index*].lazyb * tree[index].lazya + tree[index].lazyb) % P;

    tree[index*+].lazyb = (tree[index*+].lazyb * tree[index].lazya + tree[index].lazyb) % P;

    tree[index].lazya = ; tree[index].lazyb = ;

}

inline void build(LL index,LL l,LL r) {

    LL mid;

    tree[index].l = l;

    tree[index].r = r;

    tree[index].lazya = ;

    if (l == r) tree[index].sum = a[l] % P;

    else {

        mid = (l + r) >> ;

        build(index*,l,mid);

        build(index*+,mid+,r);

        pushup(index);

    }

}

inline void changea(int index,int l,int r,int x) {

    LL mid;

    pushdown(index);

    if ((tree[index].l == l) && (tree[index].r == r)) {

        tree[index].sum = tree[index].sum * x % P;

        tree[index].lazya = (tree[index].lazya * x) % P;

        tree[index].lazyb = (tree[index].lazyb * x) % P;

    }else {

            if (tree[index].l == tree[index].r) return;

        mid = (tree[index].l + tree[index].r) >> ;

           if (r <= mid) changea(index*,l,r,x);

        else if (l >= mid + ) changea(index*+,l,r,x);

        else {

            changea(index*,l,mid,x);

            changea(index*+,mid+,r,x);

        }

        pushup(index);

    }

}

inline void changeb(LL index,LL l,LL r,LL x) {

    LL mid;

    pushdown(index);

    if ((tree[index].l == l) && (tree[index].r == r)) {

        tree[index].sum = (tree[index].sum + x * (tree[index].r - tree[index].l + )) % P;

        tree[index].lazyb = (tree[index].lazyb + x) % P;

    }else {

            if (tree[index].l == tree[index].r) return;

        mid = (tree[index].l + tree[index].r) >> ;

        if (r <= mid) changeb(index*,l,r,x);

        else if (l >= mid + ) changeb(index*+,l,r,x);

        else {

            if (tree[index].l == tree[index].r) return;

            changeb(index*,l,mid,x);

            changeb(index*+,mid+,r,x);

        }

        pushup(index);

    }

}

inline LL query(LL index,LL l,LL r) {

    LL mid;

    pushdown(index);

    if ((tree[index].l == l) && (tree[index].r == r)) return tree[index].sum;

    else {

            if (tree[index].l == tree[index].r) return ;

        mid = (tree[index].l + tree[index].r) >> ;

        if (r <= mid) return query(index*,l,r);

        else if (l >= mid + ) return query(index*+,l,r);

        else return (query(index*,l,mid) + query(index*+,mid+,r)) % P;

    }

}

int main() {

    read(N); read(P);

    for (i = ; i <= N; i++) read(a[i]);

    build(,,N);

    read(Q);

    while (Q--) {

        read(opt);

        if (opt == ) {

            read(l); read(r); read(x);

            changea(,l,r,x);

        }else if (opt == ) {

            read(l); read(r); read(x);

            changeb(,l,r,x);

        }else {

            read(l); read(r);

            write(query(,l,r));

            puts("");

        }

    }    

    return ;

}