#include <bits/stdc++.h>
using namespace std;
unsigned long long rd(unsigned long long &x) {x^=(x<<13); x^=(x>>7); x^=(x<<17); return x;}
const int N=2000000,P=998244353;
#define v2 499122177ll
int Powerv2(long long y) {
	int res=1,t=v2;
	while (y) {
		if (y&1) res=1ll*res*t%P;
		t=1ll*t*t%P,y>>=1;
	}
	return res;
}

unsigned long long seed;
int n,q,x,xx,m;
int s;
long long k;
int a[N+9],b[N+9],dat[N+9];

namespace subtask1 {
	struct Matrix {
		int a[2][2];
		void set(int A,int B,int C,int D) {a[0][0]=A,a[0][1]=B,a[1][0]=C,a[1][1]=D;}
		friend Matrix operator *(Matrix a,Matrix b) {
			Matrix c;
			for (int i=0;i<2;i++)
				for (int j=0;j<2;j++) {
					c.a[i][j]=0;
					for (int k=0;k<2;k++) c.a[i][j]=(c.a[i][j]+1ll*a.a[i][k]*b.a[k][j])%P;
				}
			return c;
		}
	} g,res;
	int Fib(long long x) {
		g.set(0,1,1,1),res.set(1,0,0,1);
		while (x) {
			if (x&1) res=res*g;
			g=g*g,x>>=1;
		}
		return res.a[0][0];
	}
	void solve(int &Ans) {
		int a1=Fib(k-s+2-xx),a2=Fib(k-s+3-xx);
		Ans=1ll*((1ll*b[1]*a2+1ll*b[2]*a1)%P)*Powerv2(k-s)%P;
	}
}

namespace subtask2 {
	struct Matrix {
		int a[3][3];
		void set(int A,int B,int C,int D,int E,int F,int G,int H,int I) {a[0][0]=A,a[0][1]=B,a[0][2]=D,a[1][0]=D,a[1][1]=E,a[1][2]=F,a[2][0]=G,a[2][1]=H,a[2][2]=I;}
		friend Matrix operator *(Matrix a,Matrix b) {
			Matrix c;
			for (int i=0;i<3;i++)
				for (int j=0;j<3;j++) {
					c.a[i][j]=0;
					for (int k=0;k<3;k++) c.a[i][j]=(c.a[i][j]+1ll*a.a[i][k]*b.a[k][j])%P;
				}
			return c;
		}
	} g,res;
	int F(long long x) {
		g.set(0,0,1,1,0,1,0,1,0),res.set(1,0,0,0,1,0,0,0,1);
		while (x) {
			if (x&1) res=res*g;
			g=g*g,x>>=1;
		}
		return res.a[0][0];
	}
	void solve(int &Ans) {
		int a1,a2,a3;
		if (xx==1) a1=F(k-s+3),a2=F(k-s+2),a3=F(k-s+1);
		else if (xx==2) a1=F(k-s+4),a2=F(k-s+3),a3=F(k-s+2);
		else if (xx==3) a1=F(k-s+2),a2=F(k-s+1),a3=F(k-s);
		Ans=1ll*((1ll*b[1]*a1+1ll*b[2]*a2+1ll*b[3]*a3)%P)*Powerv2(k-s)%P;
	}
}

void solve() {
	long long k_max;
	scanf("%d%d%d%lld",&n,&q,&x,&k_max);
	for (int i=1;i<=n;i++) scanf("%d",&a[i]);
	dat[0]=a[x];
	
	s=0;
	for (int tmp=n;tmp%2==0;tmp>>=1) s++;
	int limit=max(s,min(N,50000000/n));
	for (int i=1;i<=limit;i++) {
		for (int j=1;j<=n/2;j++) b[j]=a[j]+a[n-j+1];
		for (int j=1;j<=n;j++) a[j]=v2*b[(j+1)/2]%P;
		dat[i]=a[x];
	}
	m=0,xx=0;
	for (int i=1;i<=n;i+=1<<s) {
		b[++m]=a[i];
		if (i<=x) xx=m;
	}
	s=limit;
	
	long long Res=0;
	for (int i=1;i<=q;i++) {
		k=rd(seed)%k_max;
		int Ans;
		if (k<=limit) Ans=dat[k];
		else if (m==1) Ans=b[1];
		else if (m==2) subtask1::solve(Ans);
		else if (m==3) subtask2::solve(Ans);
		Res^=1ll*Ans*i;
	}
	printf("%lld\n",Res);
}

int main() {
	freopen("noodle.in","r",stdin);
	freopen("noodle.out","w",stdout);
	int test,T;
	scanf("%d%d%llu",&test,&T,&seed);
	while (T--) solve();
	return 0;
}
