#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod=998244353;
const int inv2=(mod+1)/2;
const int NN=505;
int M[70][NN][NN],res[NN][NN],n,C[NN][NN],a[NN][NN],P[NN],val[2000005],b[2000005];
int X[NN],vec[NN],nvec[NN],VAL[2000005];
unsigned long long rd(unsigned long long &x) {
	x^=(x<<13);
	x^=(x>>7);
	x^=(x<<17);
	return x;
}
int fpow(int x,ll y) {
	int res=1;
	while (y) {
		if (y&1) res=1ll*res*x%mod;
		x=1ll*x*x%mod; y>>=1;
	}
	return res;
}
int Gauss(int n) {
	for (int i=1; i<=n; i++) {
		int p=-1;
		for (int j=i; j<=n; j++) if (a[j][i]) { p=j; break; }
		if (p==-1) { return i-1; }
		for (int j=1; j<=n+1; j++) swap(a[i][j],a[p][j]);
		int inv=fpow(a[i][i],mod-2);
		for (int j=1; j<=n+1; j++) a[i][j]=1ll*a[i][j]*inv%mod;
		for (int k=1; k<=n; k++) {
			if (k==i) continue;
			int mul=a[k][i];
			for (int j=1; j<=n+1; j++)
				a[k][j]=(a[k][j]-1ll*mul*a[i][j]%mod+mod)%mod;
		} 
		
		//for (int i=1; i<=n; i++,puts("")) for (int j=1; j<=n; j++) printf("%d ",a[i][j]); 
	}
	for (int i=1; i<=n; i++) X[i]=a[i][n+1];
	return n;
}

int main() {
	freopen("noodle.in","r",stdin);
	freopen("noodle.out","w",stdout);
	int test,T;
	unsigned long long seed;
	scanf("%d%d%llu",&test,&T,&seed);
	while (T--) {
		int q,x; ll k_max;
		scanf("%d%d%d%lld",&n,&q,&x,&k_max);
		for (int i=1; i<=n; i++) scanf("%d",&val[i]),VAL[i]=val[i];
		for (int gg=0; gg<=500; gg++) {
			P[gg]=val[x];
			//cerr<<P[gg]<<endl;
			for (int i=1; i<=n/2; i++) b[i]=(val[i]+val[n-i+1])%mod;
			for (int i=1; i<=n; i++) val[i]=b[(i+1)/2];
		}
		int m=30;
		for (int TT=1; TT<=2; TT++) {
			for (int i=1; i<=m; i++) {
				a[i][m+1]=P[i+m+30];
				for (int j=1; j<=m; j++) a[i][j]=P[i+j-1+30];
			}
			int pp=Gauss(m);
			m=pp;
		}
		
		if (m==30) {
			ll Ans=0;
			if (k_max>500) {
			for (int i=1; i<=n; i++) for (int j=1; j<=n; j++) M[0][i][j]=0;
			for (int i=1; i<=n/2; i++) {
				M[0][i<<1][i]=M[0][i<<1][n-i+1]=1;
				M[0][(i<<1)-1][i]=M[0][(i<<1)-1][n-i+1]=1;
			}
			for (int TT=1; TT<=65; TT++) {
				for (int i=1; i<=n; i++) for (int j=1; j<=n; j++) M[TT][i][j]=0;
				for (int i=1; i<=n; i++)
					for (int k=1; k<=n; k++) {
						if (!M[TT-1][i][k]) continue;
						for (int j=1; j<=n; j++)
							M[TT][i][j]=(M[TT][i][j]+1ll*M[TT-1][i][k]*M[TT-1][k][j]%mod)%mod;
					}
			}
			}
			
			for (int I=1; I<=q; I++) {
				long long k=rd(seed)%k_max;
				if (k<=500) { Ans^=(1ll*I*(1ll*P[k]*fpow(inv2,k)%mod)); }
				else {
					for (int i=1; i<=n; i++) vec[i]=VAL[i];
					for (int gg=63; gg>=0; gg--) 
						if (k&(1ll<<gg)) {
							//for (int i=1; i<=n; i++) printf("%d ",vec[i]); puts("");
							for (int i=1; i<=n; i++)
								for (int j=1; j<=n; j++)
									nvec[i]=(nvec[i]+1ll*M[gg][i][j]*vec[j]%mod)%mod;
							for (int i=1; i<=n; i++) vec[i]=nvec[i],nvec[i]=0;
							//printf("%d\n",gg);
							//for (int i=1; i<=n; i++) printf("%d ",nvec[i]); puts("");
						}
					//cerr<<vec[x]<<' '<<k<<endl;
					Ans^=(1ll*I*(1ll*vec[x]*fpow(inv2,k)%mod));
				}
			}
			cout<<Ans<<endl;
			continue;
		}
		
		
		ll Ans=0;
	//	for (int i=1; i<=m; i++) cout<<X[i]<<endl;
		for (int i=1; i<=m; i++) for (int j=1; j<=m; j++) M[0][i][j]=0;
		for (int i=1; i<m; i++) M[0][i][i+1]=1;
		for (int i=1; i<=m; i++) M[0][m][i]=X[i];
		for (int TT=1; TT<=65; TT++) {
			for (int i=1; i<=n; i++) for (int j=1; j<=n; j++) M[TT][i][j]=0;
			for (int i=1; i<=n; i++)
				for (int k=1; k<=n; k++) {	
					if (!M[TT-1][i][k]) continue;
					for (int j=1; j<=n; j++)
						M[TT][i][j]=(M[TT][i][j]+1ll*M[TT-1][i][k]*M[TT-1][k][j]%mod)%mod;
				}
		}
		
		for (int I=1; I<=q; I++) {
			long long k=rd(seed)%k_max;
			if (k<=60) Ans^=(1ll*I*(1ll*P[k]*fpow(inv2,k)%mod));
			else {
				k-=60;
				for (int i=1; i<=m; i++) vec[i]=P[i+60-1];
				for (int gg=63; gg>=0; gg--) 
					if (k&(1ll<<gg)) {
						for (int i=1; i<=m; i++)
							for (int j=1; j<=m; j++)
								nvec[i]=(nvec[i]+1ll*M[gg][i][j]*vec[j]%mod)%mod;
						for (int i=1; i<=m; i++) nvec[i]=vec[i],nvec[i]=0;
					}
				Ans^=(1ll*I*(1ll*nvec[1]*fpow(inv2,k+60)%mod));
			}
		}
		cout<<Ans<<endl;
	}
	return 0;
}
