/*
 *
 * 带lazy机制的线段树维护区间信息
 * 同时维护加法和乘法的lazy标记
 */


#include <stdio.h>
#include <algorithm>
using namespace std;


struct Data {
    long long sum;          // 区间总和
    long long lazy_add;     // 加法的lazy标记
    long long lazy_mul;     // 乘法的lazy标记
};

struct Node {
    int start;          // 区间开始位置
    int end;            // 区间结束位置
    Data data;          // 区间数据
}__global_nodes[100005*4] ;


class SegmentTree {
private:
    Node* __nodes;      // 节点数组
    int __n;            // 区间为0到n-1
    long long __mod;

    // 下沉lazy标记
    void __push_down_lazy(int node_idx) {
        Node& node = __nodes[node_idx];
        int mid = (node.start + node.end) >> 1;
        int left_idx = node_idx*2+1, right_idx = node_idx*2+2;

        if (!(node.data.lazy_add == 0 && node.data.lazy_mul == 1)) {
            // 下沉lazy标记
            __nodes[left_idx].data.sum *= node.data.lazy_mul;
            __nodes[left_idx].data.sum += (mid-node.start+1) * node.data.lazy_add;
            __nodes[left_idx].data.sum %= __mod;
            __nodes[left_idx].data.lazy_mul *= node.data.lazy_mul;
            __nodes[left_idx].data.lazy_mul %= __mod;
            __nodes[left_idx].data.lazy_add = __nodes[left_idx].data.lazy_add * node.data.lazy_mul + node.data.lazy_add;
            __nodes[left_idx].data.lazy_add %= __mod;

            __nodes[right_idx].data.sum *= node.data.lazy_mul;
            __nodes[right_idx].data.sum += (node.end - mid) * node.data.lazy_add;
            __nodes[right_idx].data.sum %= __mod;
            __nodes[right_idx].data.lazy_mul *= node.data.lazy_mul;
            __nodes[right_idx].data.lazy_mul %= __mod;
            __nodes[right_idx].data.lazy_add = __nodes[right_idx].data.lazy_add * node.data.lazy_mul + node.data.lazy_add;
            __nodes[right_idx].data.lazy_add %= __mod;

            node.data.lazy_add = 0;
            node.data.lazy_mul = 1;
        }
    }

    // 更新单个位置的数值
    void __update_single(int node_idx, int pos, long long val) {
        Node& node = __nodes[node_idx];

        if (node.start == node.end) {
            node.data.sum += val;
            node.data.sum %= __mod;

            return;
        }

        __push_down_lazy(node_idx);

        int mid = (node.start + node.end) >> 1;
        if (pos <= mid) {
            __update_single(node_idx*2+1, pos, val);
        } else {
            __update_single(node_idx*2+2, pos, val);
        }

        node.data.sum = (__nodes[node_idx*2+1].data.sum + __nodes[node_idx*2+2].data.sum) % __mod;
    }


    // 更新区间数据, 区间中每一个数据乘以val_mul, 然后加上val_add
    void __update_range(int node_idx, int start, int end, long long val_mul, long long val_add) {
        Node& node = __nodes[node_idx];
        if (node.start == start && node.end == end) {
            node.data.sum *= val_mul;
            node.data.sum += val_add * (node.end - node.start + 1);
            node.data.sum %= __mod;

            node.data.lazy_mul *= val_mul;
            node.data.lazy_mul %= __mod;
            node.data.lazy_add = node.data.lazy_add * val_mul + val_add;
            node.data.lazy_add %= __mod;
            return;
        }

        __push_down_lazy(node_idx);

        int mid = (node.start + node.end) >> 1;
        if (end <= mid) {
            __update_range(node_idx*2+1, start, end, val_mul, val_add);
        } else if (start >= mid + 1) {
            __update_range(node_idx*2+2, start, end, val_mul, val_add);
        } else {
            __update_range(node_idx*2+1, start, mid, val_mul, val_add);
            __update_range(node_idx*2+2, mid+1, end, val_mul, val_add);
        }

        node.data.sum = (__nodes[node_idx*2+1].data.sum + __nodes[node_idx*2+2].data.sum) % __mod;
    }

    // 获取区间统计信息
    long long __get_val(int node_idx, int start, int end) {
        Node& node = __nodes[node_idx];
        if (node.start == start && node.end == end) {
            return node.data.sum % __mod;
        }

        __push_down_lazy(node_idx);

        int mid = (node.start + node.end) >> 1;
        if (end <= mid) {
            return __get_val(node_idx*2+1, start, end);
        } else if (start >= mid+1) {
            return __get_val(node_idx*2+2, start, end);
        } else {
            long long val1 = __get_val(node_idx*2+1, start, mid);
            long long val2 = __get_val(node_idx*2+2, mid+1, end);
            return (val1 + val2) % __mod;
        }
    }

public:
    SegmentTree(int n, Node* pnodes, long long MOD) {
        __n = n;
        __nodes = pnodes;
        __nodes[0] = {0, n-1, 0};
        __mod = MOD;

        for (int i = 0; i < __n << 2; i++) {
            if (__nodes[i].start == __nodes[i].end and __nodes[i].end == __n-1) {
                break;
            }

            int mid = (__nodes[i].start + __nodes[i].end) / 2;
            __nodes[i*2+1] = {__nodes[i].start, mid, {0, 1, 0}};
            __nodes[i*2+2] = {mid+1, __nodes[i].end, {0, 1, 0}};
        }
    }

    // 更新单个数据接口
    void update_single(int pos, long long val) {
        __update_single(0, pos, val);
    }

    // 更新区间数据接口
    void update_range(int start, int end, long long val_mul, long long val_add) {
        __update_range(0, start, end, val_mul, val_add);
    }

    // 获取区间统计数据接口
    long long get_val(int start, int end) {
        return __get_val(0, start, end);
    }
};

int main() {
    //freopen("/Users/grh/Programming/CLionProjects/Test/data.txt", "r", stdin);

    int n, m, start, end, cmd;
    long long MOD, val;

    scanf("%d %lld", &n, &MOD);
    SegmentTree tree(n, __global_nodes, MOD);

    for (int i = 0; i < n; i++) {
        scanf("%lld", &val);
        tree.update_single(i, val);
    }

    scanf("%d", &m);
    for (int i = 0; i < m; i++) {
        scanf("%d", &cmd);
        if (cmd == 1) {
            scanf("%d %d %lld", &start, &end, &val);
            tree.update_range(start-1, end-1, val, 0);
        } else if (cmd == 2) {
            scanf("%d %d %lld", &start, &end, &val);
            tree.update_range(start-1, end-1, 1, val);
        } else {
            scanf("%d %d", &start, &end);
            printf("%lld\n", tree.get_val(start-1, end-1) % MOD);
        }
    }

    return 0;
}