#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
typedef pair<LL, LL> PII;

LL exgcd(LL a, LL b, LL &x, LL &y)
{
	if (!b) {
		x = 1;
		y = 0;
		return a;
	}
	LL res = exgcd(b, a % b, x, y);
	LL t = x;
	x = y;
	y = t - (a / b) * y;
	return res;
}

LL POW(LL a, LL b, LL MOD)
{
	LL res = 1;
	while (b) {
		if (b & 1) res = res * a % MOD;
		a = a * a % MOD;
		b >>= 1;
	}
	return res;
}

vector<PII> get(int m) 
{
	vector<PII> res;
	for (int i = 2; i * i <= m; i++) {
		if (m % i == 0) {
			res.push_back(PII(i, 0));
			while (m % i == 0) {
				m /= i;
				res.back().second++;
			}
		}
	}
	if (m > 1) res.push_back(PII(m, 1));
	return res;
}

LL inverse(LL a, LL MOD)
{
	LL x, y;
	exgcd(a, MOD, x, y);
	x = (x + MOD) % MOD;
	return x;
}

int data[10010];
int    m[10010];

class SegTree {
public:
	static const int SIZE = 10010;
	struct node {
		LL a, b;
		LL mul, add;
	}T[20][SIZE << 2];	///

	void update(int c, int k, int MOD) {
		T[c][k].a = (T[c][k << 1].a * T[c][k << 1 | 1].a) % MOD;
		T[c][k].b = (T[c][k << 1].b + T[c][k << 1 | 1].b);
	}
	void down(int c, int k, int MOD) {
		T[c][k << 1].mul *= T[c][k].mul;
		T[c][k << 1].mul %= MOD;
		T[c][k << 1 | 1].mul *= T[c][k].mul;
		T[c][k << 1 | 1].mul %= MOD;
		T[c][k].mul = 1;

		T[c][k << 1].add += T[c][k].add;
		T[c][k << 1 | 1].add += T[c][k].add;
		T[c][k].add = 0;
	}
	void set(int c, int k, int pos, int L, int R, LL a, LL b, LL MOD) {
		T[c][k].mul = 1;
		T[c][k].add = 0;
		if (L == R) {
			T[c][k].a = a;
			T[c][k].b = b;
			return;
		}
		int mid = (L + R) >> 1;
		if (pos <= mid) set(c, k << 1, pos, L, mid, a, b, MOD);
		else set(c, k << 1 | 1, pos, mid + 1, R, a, b, MOD);
		update(c, k, MOD);
	}
	PII get(int c, int k, int qL, int qR, int L, int R, LL MOD) {
		if (qL > R || qR < L) return PII(1, 0);
		if (qL <= L && R <= qR) {
			return PII(T[c][k].a, T[c][k].b);
		}
		down(c, k, MOD);
		int mid = (L + R) >> 1;
		PII c0 = get(c, k << 1, qL, qR, L, mid, MOD);
		PII c1 = get(c, k << 1 | 1, qL, qR, mid + 1, R, MOD);
		update(c, k, MOD);
		return PII(c0.first * c1.first % MOD, (c0.second + c1.second));
	}
	void modify(int c, int k, int qL, int qR, int L, int R, LL a, LL b, LL MOD, int tag) {
		if (qL > R || qR < L) return;
		int len = qR - qL + 1;
		if (tag == 1) {
			T[c][k].a = T[c][k].a * POW(a, len, MOD) % MOD;
			T[c][k].b += b * len;
		}
		if (tag == 2) {
			T[c][k].a = T[c][k].a * inverse( POW(a, len, MOD), MOD) % MOD;
			T[c][k].b -= b * len;
		}
		if (qL <= L && R <= qR) {
			if (tag == 1) {
				T[c][k].mul = T[c][k].mul * a % MOD;
				T[c][k].add = T[c][k].add + b;
			}
			if (tag == 2) {
				T[c][k].mul = T[c][k].mul * inverse(a, MOD) % MOD;
				T[c][k].add = T[c][k].add - b;
			}
			return;
		}
		down(c, k, MOD);
		int mid = (L + R) >> 1;
		modify(c, k << 1, qL, qR, L, mid, a, b, MOD, tag);
		modify(c, k << 1 | 1, qL, qR, mid + 1, R, a, b, MOD, tag);
		update(c, k, MOD);
	}
}ST;

LL rev(PII now, LL p, LL MOD)
{
	LL res = now.first % MOD;
	res = res * POW(p, now.second, MOD) % MOD;
	return res;
}

inline LL mod(LL x, LL y) {
	LL res = x % y;
	if (res < 0) res += y;
	return res;
}

LL solve(int n, vector<LL> &c, vector<LL> &m) {
	LL ans = c[0], LCM = m[0], x, y, g, mm;
	for (int i = 1; i < n; i++) {
		g = exgcd(LCM, m[i], x, y);
        ans = mod( ans + LCM * mod( (c[i] - ans) / g * x, m[i]/g ), LCM / g * m[i]);
		LCM = LCM / g * m[i];
	}
	return mod(ans, LCM);
}

PII gao(LL now, LL p)
{
	int cnt = 0;
	while (now % p == 0) {
		now /= p;
		cnt++;
	}
	return PII(now, cnt);
}

int main()
{
	int T;
	scanf("%d", &T);
	for (int cas = 1; cas <= T; cas++) {
		printf("Case #%d:\n", cas);
		int n, MOD;
		scanf("%d%d", &n, &MOD);
		vector<PII> U = get(MOD);
		int tot = U.size();
		for (int i = 0; i < tot; i++) {
			m[i] = 1;
			for (int j = 0; j < U[i].second; j++) m[i] *= U[i].first;
		}

		for (int i = 1; i <= n; i++) {
			scanf("%d", &data[i]);
			for (int j = 0; j < tot; j++) {
				PII tmp = gao(data[i], U[j].first);
				ST.set(j, 1, i, 1, n, tmp.first, tmp.second, m[j]);
			}
		}

		int Q;
		scanf("%d", &Q);
		while (Q--) {
			char opt[10];
			int L, R;
			scanf("%s%d%d", opt, &L, &R);
			if (*opt == 'Q') {
				vector<LL> A, B;
				for (int i = 0; i < tot; i++) {
					PII now = ST.get(i, 1, L, R, 1, n, m[i]);
					A.push_back( rev(now, U[i].first, m[i]) );
					B.push_back(m[i]);
				}
				LL ans = solve(tot, A, B);
				printf("%lld\n", ans);
			}
			if (*opt == 'M') {
				int X;
				scanf("%d", &X);
				for (int i = 0; i < tot; i++) {
					PII tmp = gao(X, U[i].first);
					ST.modify(i, 1, L, R, 1, n, tmp.first, tmp.second, m[i], 1);
				}
			}
			if (*opt == 'D') {
				int X;
				scanf("%d", &X);
				for (int i = 0; i < tot; i++) {
					PII tmp = gao(X, U[i].first);
					ST.modify(i, 1, L, R, 1, n, tmp.first, tmp.second, m[i], 2);
				}
			}
		}
	}
	return 0;
}

