#include<bits/stdc++.h>
using namespace std;
bool f1;
#define LL long long
#define Max(a,b) ((a)<(b))&&((a)=(b))
#define Min(a,b) ((a)>(b))&&((a)=(b))
int rd() {
	int res=0;char ch;
	bool f=false;
	while(ch=getchar(),ch<48||ch>57)if(ch=='-')f=true;
	do res=(res<<1)+(res<<3)+(ch^48);
	while(ch=getchar(),ch>47&&ch<58);
	return f?-res:res;
}
unsigned long long Read(unsigned long long &x) {
	x ^= (x << 13);
	x ^= (x >> 7);
	x ^= (x << 17);
	return x;
}
const int M=2e6+5;
const int P=998244353;
const int inv2=499122177;
int n,q,x;
long long k_max,k;
int a[M];
void Add(int &x,int y) {x+=y;(x>=P)&&(x-=P);}
LL Ans;
int test, T;
unsigned long long seed;
namespace P10 {
	int ans[M];
	void Solve() {
		int m=n/2;ans[0]=a[x];
		for(int i=1; i<=k_max; ++i) {
			for(int j=1; j<=m; ++j)Add(a[j],a[n-j+1]);	
			for(int j=n; j; j-=2)a[j]=a[j-1]=1LL*a[j/2]*inv2%P;
			ans[i]=a[x];
		}
		for(int i = 1; i <= q; i ++) {
			k = Read(seed) % k_max;
			Ans^=(1LL*i*ans[k]);
		}
		printf("%lld\n",Ans);
	}
}
bool Check(int x) {
	int cnt=0;
	for(int i=0; i<=21; ++i)
		if(x&(1<<i))cnt++;
	return cnt==1;
}
namespace P15 {
	int ans[M];
	void Solve() {
		int m=n/2;ans[0]=a[x];
		for(int i=1; i<=21; ++i) {
			for(int j=1; j<=m; ++j)Add(a[j],a[n-j+1]);	
			for(int j=n; j; j-=2)a[j]=a[j-1]=1LL*a[j/2]*inv2%P;
			ans[i]=a[x];
		}
		for(int i = 1; i <= q; i ++) {
			k = Read(seed) % k_max;
			if(k>21)k=21;
			Ans^=(1LL*i*ans[k]);
		}
		printf("%lld",Ans);
	}
}
namespace P30 {
	struct MAT {
		int B[155][155];
		void Clear() {memset(B,0,sizeof B);}
		MAT operator *(const MAT &_) const{
			MAT C;C.Clear();
			for(int k=1; k<=n; ++k)
				for(int i=1; i<=n; ++i)
					for(int j=1; j<=n; ++j)
						C.B[k][i]=(C.B[k][i]+1LL*B[k][j]*_.B[j][i])%P;
			return C;
		}
	}F[65],as,tmp;
	void Solve() {
		F[0].Clear();
		for(int i=1; i<=n; ++i)F[0].B[i][(i+1)/2]=F[0].B[i][n-(i+1)/2+1]=inv2;
		for(int i=1; i<=60; ++i)F[i]=F[i-1]*F[i-1];
		for(int i = 1; i <= q; i++) {
			as.Clear();bool flag=false;
			k = Read(seed) % k_max;
			for(int j=0; j<=60; ++j)
				if((1LL<<j)&k) {
					if(!flag) {as=F[j],flag=true;continue;}
					tmp.Clear();	
					for(int z=1; z<=n; ++z)
						for(int y=1; y<=n; ++y)
							tmp.B[x][z]=(tmp.B[x][z]+1LL*as.B[x][y]*F[j].B[y][z])%P;
					as=tmp;
				}
			int res=0;
			for(int j=1; j<=n; ++j) {
				res=(res+1LL*as.B[x][j]*a[j])%P;
//				cout<<as.B[x][j]<<" "<<x<<" "<<j<<" "<<endl;
			}
			if(k==0)res=a[x];
			Ans^=(1LL*i*res);
		}
		printf("%lld\n",Ans);
	}
}
void Init() {
	scanf("%d%d%llu", &test, &T, &seed);
	for(int Case = 1; Case <= T; Case ++) {
		Ans=0;
		scanf("%d%d%d%lld", &n, &q, &x, &k_max);
		for(int i = 1; i <= n; i ++)a[i]=rd();
		if((k_max<=500&&n<=500)||k_max<=10)P10::Solve();
		else if(Check(n))P15::Solve();
		else if(n<=150&&q<=150)P30::Solve();
	}
}
bool f2;
int main() {
//	printf("%lf\n",(&f2-&f1)/1024.0/1024.0);
	freopen("noodle.in","r",stdin);
	freopen("noodle.out","w",stdout);
	Init();
	return 0;	
}
