#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 a[2100000],b[2100000],val[2100000];
ull rd(ull &x){
	x^=(x<<13);
	x^=(x>>7);
	x^=(x<<17);
	return x;
}
void solve(int n,int q,int x,ll k_max){
	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 n,int q,int x,ll k_max){
	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 main(){
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	int t; cin>>t>>T>>seed;
	for (int Case=1;Case<=T;Case++){
		int n,q,x; ll k_max;
		cin>>n>>q>>x>>k_max;
		for (int i=1;i<=n;i++) cin>>a[i];
		if (n!=98304) solve(n,q,x,k_max);
		else solve2(n,q,x,k_max);
	}
	return 0;
}
