#include<iostream>
#include<vector>
using namespace std;
typedef long long ll;
typedef vector<ll> vll;
struct st {
	ll a,b;
	vll tree, add, mul;
	st(ll m, ll p) {
		a = p;
		b=m;
		tree.resize(m + 1);
		add.resize(m + 1);
		mul.resize(m + 1);
		for (int i = 0; i <= m; ++i) {
			mul[i] = 1;
			add[i] = 0;
		}
	}
	const long long p = a;
	bool in(int l, int r, int x, int y) {
		return l <= x && r >= y;
	}
	bool out(int l, int r, int x, int y) {
		return l > y || r < x;
	}
	void makestage(int node, int l, int r, int type, ll val) {
		if (type == 1) {
			mul[node] = (mul[node] * val) % p;
			add[node] = (add[node] * val) % p;
			tree[node] = (tree[node] * val) % p;
		}
		else {
			add[node] = (add[node] + val) % p;
			tree[node] = (tree[node] + val * (r - l + 1)) % p;
		}
	}
	void pushup(int node) {
		tree[node] = (tree[node * 2] + tree[node * 2 + 1]) % p;
	}
	void pushdown(int node, int l, int r) {
		int mid = (l + r) / 2;
		makestage(2 * node, l, mid, 1, mul[node]);
		makestage(2 * node, l, mid, 2, add[node]);
		makestage(2 * node + 1, mid + 1, r, 1, mul[node]);
		makestage(2 * node + 1, mid + 1, r, 2, add[node]);
		mul[node] = 1;
		add[node] = 0;
	}
/*	void build(vll arr, int node, int l, int r) {
		if (l == r) {
			tree[node] = arr[l];  
			mul[node] = 1;
			add[node] = 0;
			return;
		}
		int mid = (l + r) / 2;
		build(arr, 2 * node, l, mid);
		build(arr, 2 * node + 1, mid + 1, r);
		pushup(node);
	}*/
	void build(vector<ll>& arr, int node, int left, int right) {
		if (left == right) {
			tree[node]= arr[left];
			return;
		}
		int mid = (left + right) >> 1;
		build(arr, node << 1, left, mid);
		build(arr, node << 1 | 1, mid + 1, right);
		pushup(node);
	}
	void buildTree(vector<ll>& arr) {
		build(arr, 1, 1, b);
	}
	ll query(int node, int l, int r, int x, int y) {
		if (l > y || r < x) {
			return 0;
		}
		if (in(l, r, x, y)) {
			return tree[node];
		}
		pushdown(node, l, r);
		int mid = (l + r) / 2;
		return (query(2 * node, l, mid, x, y) + query(2 * node + 1, mid + 1, r, x, y)) % p;
	}
	void update(int node, int l, int r, int x, int y, ll val, int type) {
		if (in(l, r, x, y)) {
			makestage(node, l, r, type, val);
		}
		else if (!out(l, r, x, y)) {
			pushdown(node, l, r);
			int mid = (l + r) / 2;
			update(node * 2, l, mid, x, y, val, type);
			update(node * 2 + 1, mid + 1, r, x, y, val, type);
			pushup(node);
		}
	}
};
int main() {
	int n, q, m;
	cin >> n >> q >> m;
	vll arr(n+1);
	for (int i = 1; i <= n; ++i) {
		cin >> arr[i];
	}
	st tree(n, m);
	tree.buildTree(arr);
	for (int i = 1; i <= q; ++i) {
		int t, x, y;
		cin >> t >> x >> y;
		if (t!= 3) {
			ll k;
			cin >> k;
			tree.update(1, 1, n, x, y, k, t);
		}
		else {
			cout << tree.query(1, 1, n, x, y) << endl;
		}
	}
	return 0;
}