#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
const int Mod=998244353;
const int inv2=(Mod+1)/2;
const int inv3=(Mod+1)/3;
const int inv8=(7ll*Mod+1)/8;
int T; ull seed;
int n,q,x; ll k_max;
int a[2100000],b[2100000],val[2100000];
struct node{
	int v[210][210];
	void clr(){
		for (int i=1;i<=n;i++)
			for (int j=1;j<=n;j++)
				v[i][j]=0;
	}
	node operator*(const node &a) const{
		node res;
		for (int i=1;i<=n;i++)
			for (int j=1;j<=n;j++){
				res.v[i][j]=0;
				for (int k=1;k<=n;k++) res.v[i][j]=(res.v[i][j]+1ll*v[i][k]*a.v[k][j])%Mod;
			}
		return res;
	}
} B[66];
ull rd(ull &x){
	x^=(x<<13);
	x^=(x>>7);
	x^=(x<<17);
	return x;
}
void solve(){
	val[0]=a[x];
	ll mx=0;
	for (int j=1;j<=k_max;j++){
		bool f=true;
		for (int i=1;i<=n;i++){
			b[i]=1ll*(a[(i+1)>>1]+a[n-((i+1)>>1)+1])*inv2%Mod;
			if (b[i]!=a[i]) f=false;
		}
		val[j]=b[x];
		mx=j; if (f) break;
		for (int i=1;i<=n;i++) a[i]=b[i];
	}
	ll ans=0;
	for (int i=1;i<=q;i++){
		ll k=rd(seed)%k_max;
		k=min(k,(ll)mx); ans^=1ll*val[k]*i;
	}
	cout<<ans<<'\n';
}
ll qpow(ll x,ll a){
	ll res=1;
	while (a){
		if (a&1) res=res*x%Mod;
		x=x*x%Mod; a>>=1;
	}
	return res;
}
int calc(int n,int t,int v){
//	cerr<<Mod-(Mod+1-qpow(Mod-2,n))*inv3%Mod<<'\n'; 
	return ((Mod-(Mod+1-qpow(Mod-2,n))*inv3%Mod)%Mod*t%Mod+v)*qpow(qpow(Mod-2,n),Mod-2)%Mod;
}
void solve2(){
	int s=0;
	for (int i=1;i<=n;i++) s=(s+a[i])%Mod;
	val[0]=a[x];
	for (int j=1;j<=18;j++){
		for (int i=1;i<=n;i++)
			b[i]=1ll*(a[(i+1)>>1]+a[n-((i+1)>>1)+1])*inv2%Mod;
		val[j]=b[x];
		for (int i=1;i<=n;i++) a[i]=b[i];
	}
	int t=1ll*s*inv8%Mod,v=a[1];
	for (int i=1;i<=10;i++) cerr<<calc(i,t,v)<<'\n';
	ll ans=0;
	for (int i=1;i<=q;i++){
		ll k=rd(seed)%k_max;
		if (k<=18) ans^=1ll*val[k]*i;
		else if (x<=(n&(-n))) ans^=1ll*calc(k-18,t,v)*i;
		else ans^=1ll*(((t-calc(k-18,t,v)*2)%Mod+Mod)%Mod)*i;
	}
	cout<<ans<<'\n';
}
int t[2100000],tq[2100000];
ll calc(ll k,int x){
	for (int i=1;i<=n;i++) t[i]=a[i];
	for (int b=0;b<=60;b++)
		if ((k>>b)&1){
			for (int i=1;i<=n;i++){
				tq[i]=0;
				for (int k=1;k<=n;k++)
					tq[i]=(tq[i]+1ll*B[b].v[i][k]*t[k])%Mod;
			}
			for (int i=1;i<=n;i++) t[i]=tq[i];
		}
	return t[x];
}
void solve3(){
	B[0].clr();
	for (int i=1;i<=n;i++){
		B[0].v[i][(i+1)>>1]=inv2;
		B[0].v[i][n-((i+1)>>1)+1]=inv2;
	}
	for (int i=1;i<=60;i++) B[i]=B[i-1]*B[i-1];
	ll ans=0;
	for (int i=1;i<=q;i++){
		ll k=rd(seed)%k_max;
		ans^=1ll*calc(k,x)*i;
	}
	cout<<ans<<'\n';
}
int main(){
	freopen("noodle.in","r",stdin);
	freopen("noodle.out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	int t; cin>>t>>T>>seed;
	for (int Case=1;Case<=T;Case++){
		cin>>n>>q>>x>>k_max;
		for (int i=1;i<=n;i++) cin>>a[i];
		if (n<=150) solve3();
		else if (n!=98304) solve();
		else solve2();
	}
	return 0;
}

/*
0 1 13
24 20 19 50
8 1 6 6 2 7 3 4 8 7 4 2 5 4 1 4 2 6 3 2 6 6 2 3


0 2 13
4 2 1 3
1 4 2 3
6 2 3 3
6 2 5 3 1 4
*/
