#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
#include <numeric>
#include <cassert>
#include <cmath>
#include <map>
#include <set>
 
using namespace std;
typedef long long LL;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<LL> VL;
typedef vector<VL> VVL;
 
#define FOR(k,a,b) for(int k(a); k < (b); ++k)
#define FORD(k,a,b) for(int k(b-1); k >= (a); --k)
#define REP(k,a) for(int k=0; k < (a); ++k)
#define ABS(a) ((a)>0?(a):-(a))
#define EPS 1e-9
#define INF 1e9
 
class MersenneTwister
{
	static const size_t MT_SIZE = 624;
	static const size_t MT_M = 397;
	static const size_t MT_MSB = 0x80000000U;
	static const size_t MT_LS31B = 0x7FFFFFFFU;
	static const size_t MT_A = 2567483615U;
	vector<size_t> history;
	int pos;
public:
	MersenneTwister(size_t seed = 0) { history.resize(MT_SIZE);reset(); }
	inline void reset(size_t seed = 0)
	{
		pos = 0;
		history[0] = seed;
		FOR(i, 1, MT_SIZE)
			history[i] = 1812433253U * (history[i - 1] ^ (history[i - 1] >> 30)) + i;
	}
	inline void generate()
	{
		size_t tmp;
		REP(i, MT_SIZE - MT_M)
		{
			tmp = (history[i] & MT_MSB) + (history[i + 1] & MT_LS31B);
			history[i] = history[i + MT_M] ^ (tmp >> 1) ^ (MT_A&-(tmp & 1));
		}
		FOR(i, MT_SIZE - MT_M, MT_SIZE - 1)
		{
			tmp = (history[i] & MT_MSB) + (history[i + 1] & MT_LS31B);
			history[i] = history[i + MT_M - MT_SIZE] ^ (tmp >> 1) ^ (MT_A&-(tmp & 1));
		}
		tmp = (history[MT_SIZE - 1] & MT_MSB) + (history[0] & MT_LS31B);
		history[MT_SIZE - 1] = history[MT_M - 1] ^ (tmp >> 1) ^ (MT_A&-(tmp & 1));
	}
	inline size_t rand()
	{
		if (pos == 0) generate();
		size_t ans = history[pos++];
		if (pos == 624) pos = 0;
		ans ^= ans >> 11;
		ans ^= (ans << 7) & 2636928640U;
		ans ^= (ans << 15) & 4022730752U;
		ans ^= ans >> 18;
		return ans;
	}
	inline size_t rand(size_t A, size_t B)
	{
		return A + rand() % (B - A + 1);
	}
};
MersenneTwister mt;
// random generator function:
ptrdiff_t myrandom(ptrdiff_t i) { return mt.rand() % i; }
 
// pointer object to it:
ptrdiff_t(*p_myrandom)(ptrdiff_t) = myrandom;
 
 
LL MODMUL(LL a, LL b, LL MOD)
{
	long double r = a;
	r *= b;
	LL c = r / MOD;
	a *= b;
	a -= c*MOD;
	a %= MOD;
	return a < 0 ? a + MOD : a;
}
 
struct FOURS
{
	LL a, b, c, d;
	static LL P;
	static VI w1, w2;
	static void Init(LL _P)
	{
		P = _P;
		int Limit = 1e6 + 1;
		w1.resize(Limit, -1), w2.resize(Limit, -1);
		REP(i, 1001) REP(j, 1001)
		{
			int iijj = i*i + j*j;
			if (iijj < w1.size() && w1[iijj] == -1)
				w1[iijj] = i, w2[iijj] = j;
		}
	}
	static FOURS get(int val)
	{
		FOURS res;
		if (w1[val] != -1)
		{
			res.a = w1[val];
			res.b = w2[val];
			res.c = res.d = 0;
		}
		else
		{
			while (1)
			{
				int z = mt.rand(1, val - 1);
				int rem = val - z;
				if (w1[z] != -1 && w1[rem] != -1)
				{
					res.a = w1[z];
					res.b = w2[z];
					res.c = w1[rem];
					res.d = w2[rem];
					break;
				}
			}
		}
		return res;
	}
	static FOURS combine(const FOURS& u, const FOURS& v)
	{
		FOURS res;
		res.a = (MODMUL(u.a, v.a, P) + MODMUL(u.b, v.b, P) + MODMUL(u.c, v.c, P) + MODMUL(u.d, v.d, P)) % P;
		res.b = (2 * P + MODMUL(u.a, v.b, P) - MODMUL(u.b, v.a, P) + MODMUL(u.c, v.d, P) - MODMUL(u.d, v.c, P)) % P;
		res.c = (2 * P + MODMUL(u.a, v.c, P) - MODMUL(u.b, v.d, P) - MODMUL(u.c, v.a, P) + MODMUL(u.d, v.b, P)) % P;
		res.d = (2 * P + MODMUL(u.a, v.d, P) + MODMUL(u.b, v.c, P) - MODMUL(u.c, v.b, P) - MODMUL(u.d, v.a, P)) % P;
		return res;
	}
};
 
LL FOURS::P;
VI FOURS::w1;
VI FOURS::w2;
 
struct SEGMENT_TREE
{
	int N;
	LL P;
	vector<FOURS> data;
 
	SEGMENT_TREE(const VL& _data, LL _P)
	{
		N = _data.size();
		P = _P;
		data.clear();
		data.resize(2 * N);
		FOURS::Init(P);
		REP(i, N)
		{
			data[N + i] = FOURS::get(_data[i]);
		}
		for (int i = N - 1;i > 0;--i)
		{
			data[i] = FOURS::combine(data[2*i], data[2*i+1]);
		}
	}
	
	void update(int pos, LL value)
	{
		pos += N;
		data[pos] = FOURS::get(value);
		
		do {
			if (pos /= 2)
			{
				data[pos] = FOURS::combine(data[2 * pos], data[2 * pos + 1]);
			}
 
		} while (pos);
	}
	FOURS query(int l, int r)
	{
		FOURS res;
		res.a = res.b = res.c = res.d = 0;
		bool inited = false;
 
		for (l += N, r += N; l < r;l /= 2, r /= 2)
		{
			if (l & 1)
			{
				res = inited ? FOURS::combine(res, data[l]) : data[l];
				l++;
				inited = 1;
			}
			if (r & 1)
			{
				res = inited ? FOURS::combine(res, data[r - 1]) : data[r-1];
				r--;
				inited = 1;
			}
		}
		return res;
	}
};
 
int main(int argc, char** argv) {
#ifdef HOME
	freopen("in.txt", "rb", stdin);
	freopen("out.txt", "wb", stdout);
#endif
	int T,N, Q, a, b, c;
	LL P;
	scanf("%d", &T);
	assert(T>0 && T<=3);
	while(T--)
	{
	scanf("%d %d %lld", &N, &Q, &P);
	assert(N>0 && N<=100000);
	assert(P>0 && P<=1000000000000LL);
	assert(Q>0 && Q<=100000);
	vector<LL> in(N);
	REP(i, N)
	{
		scanf("%lld", &in[i]);
		assert(in[i]>0 && in[i]<=1000000);
	}
	SEGMENT_TREE stree(in, P);
	REP(q, Q)
	{
		scanf("%d %d %d", &a, &b, &c);
		assert(a>0 && a<=2);
		if (a == 1)
		{
			stree.update(b - 1, c);
			assert(b>0 && b<=100000);
			assert(c>0 && c<=1000000);
		}
		else
		{
			FOURS r = stree.query(b - 1, c);
			assert(b>0 && b<=100000);
			assert(b<=c);
			assert(c>0 && c<=100000);
			//LL res = (MODMUL(r.a, r.a, P) + MODMUL(r.b, r.b, P) + MODMUL(r.c, r.c, P) + MODMUL(r.d, r.d, P)) % P;
			printf("%lld %lld %lld %lld\n", r.a, r.b, r.c, r.d);
			
		}
	}
	}
	return 0;
}