#include <bits/stdc++.h>
using namespace std;

#define ll long long

const int N = 1e5 + 5, MAXA = 1005;

ll p;

struct data{
	ll a[4];
} seg[4*N], dummy;

pair<int, int> pair_sum[MAXA + 5];
pair<pair<int, int>, pair<int, int> > quad_sum[MAXA + 5];

int A[N];

ll add(ll a, ll b){
	ll res = (a + b) % p;
	if(res < 0)	res += p;
	return res;
}

ll mul2 (ll a, ll b, ll m) {
  ll q = (ll) ((long double) a * (long double) b / (long double) m);
  ll r = a * b - q * m;
  return (r + 5 * m)% m;
}

ll mult(ll a, ll b){
	ll ret = mul2(abs(a), abs(b), p);
	if(a < 0)	ret *= -1;
	if(b < 0)	ret *= -1;
	if(ret < 0)	ret += p;
	return ret;
}

data combine(data A, data B){
	if(A.a[0] == -1)	return B;
	else if(B.a[0] == -1)	return A;

	//(a1^2 + a2^2 + a3^2 + a4^2) * (b1^2 + b2^2 + b3^2 + b4^2) = 
	//(a1b1 + a2b2 + a3b3 + a4b4)^2 + (a1b2 - a2b1 + a3b4 - a4b3)^2 + 
	//(a1b3 - a2b4 - a3b1 + a4b2)^2 + (a1b4 + a2b3 - a3b2 - a4b1)^2

	data C;
	C.a[0] = add(add(mult(A.a[0], B.a[0]), mult(A.a[1], B.a[1])), add(mult(A.a[2], B.a[2]), mult(A.a[3], B.a[3])));
	C.a[1] = add(add(mult(A.a[0], B.a[1]), mult(-A.a[1], B.a[0])), add(mult(A.a[2], B.a[3]), mult(-A.a[3], B.a[2])));
	C.a[2] = add(add(mult(A.a[0], B.a[2]), mult(-A.a[1], B.a[3])), add(mult(-A.a[2], B.a[0]), mult(A.a[3], B.a[1])));
	C.a[3] = add(add(mult(A.a[0], B.a[3]), mult(A.a[1], B.a[2])), add(mult(-A.a[2], B.a[1]), mult(-A.a[3], B.a[0])));
	return C;
}

data break_apart(int x){
	data tmp;
	tmp.a[0] = quad_sum[x].first.first % p, tmp.a[1] = quad_sum[x].first.second % p;
	tmp.a[2] = quad_sum[x].second.first % p, tmp.a[3] = quad_sum[x].second.second % p;
	return tmp;
}

void build(int nd, int l, int r){
	if(l != r){
		int mid = (l + r)/2;
		build(nd*2, l, mid);
		build(nd*2 + 1, mid + 1, r);
		seg[nd] = combine(seg[nd*2], seg[nd*2 + 1]);
	}
	else	seg[nd] = break_apart(A[l]);
}

void update(int nd, int l, int r, int x){
	if(l == r)	seg[nd] = break_apart(A[l]);
	else{
		int mid = (l + r)/2;
		if(x > mid)	update(nd*2 + 1, mid + 1, r, x);
		else update(nd*2, l, mid, x);
		seg[nd] = combine(seg[nd*2], seg[nd*2 + 1]);
	}
}

data query(int nd, int l, int r, int x, int y){
	if(l > y or r < x)	return dummy;
	else if(l >= x and r <= y)	return seg[nd];
	else{
		int mid = (l + r)/2;
		return combine(query(nd*2, l, mid, x, y), query(nd*2 + 1, mid + 1, r, x, y));
	}
}

void solve(){
	int n, q, type, l, r;

	scanf("%d %d %lld", &n, &q, &p);
	for(int i = 1; i <= n; i++)	scanf("%d", &A[i]);

	build(1, 1, n);
	
	while(q--){
		scanf("%d %d %d", &type, &l, &r);
		if(type == 1){
			A[l] = r;
			update(1, 1, n, l);
		}
		else{
			data tmp = query(1, 1, n, l, r);
			printf("%lld %lld %lld %lld\n", tmp.a[0], tmp.a[1], tmp.a[2], tmp.a[3]);
		}
	}
}

int main(){

	for(int i = 0; i <= MAXA; i++)	pair_sum[i] = make_pair(-1, -1);

	vector<int> V;

	for(int i = 0; i * i <= MAXA; i++)	V.push_back(i);

	for(int i = 0; i < V.size(); i++){
		for(int j = 0; j < V.size(); j++){
			int tot = V[i]*V[i] + V[j]*V[j];
			if(tot <= MAXA and pair_sum[tot] == make_pair(-1, -1))
				pair_sum[tot] = {V[i], V[j]};
		}
	}

	for(int i = 0; i <= MAXA; i++){
		for(int j = 0; j <= i; j++){
			if(pair_sum[j] != make_pair(-1, -1) and pair_sum[i - j] != make_pair(-1, -1)){
				quad_sum[i] = {pair_sum[j], pair_sum[i - j]};
				break;
			}
		}
	}

	dummy.a[0] = dummy.a[1] = dummy.a[2] = dummy.a[3] = -1;

	int t;
	scanf("%d", &t);
	while(t--)	solve();
	return 0;
}