#include <bits/stdc++.h>
using namespace std;
#define ull unsigned long long
#define ll long long
const int N=2e6+5;
const ll mod=998244353;
int n,q,x,k_max,a[N],val[25][N];
struct nade{
	int a[55][55];
	nade(){
		for(int i=1;i<=n;i++)	
			for(int j=1;j<=n;j++)
				a[i][j]=0;
	}
	void init(){
		for(int i=1;i<=n;i++)a[i][i]=1;
	}
	nade operator * (nade b){
		nade c;
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++)
				for(int k=1;k<=n;k++)
					c.a[i][j]=(c.a[i][j]+1ll*a[i][k]*b.a[k][j])%mod;
		return c;
	}
};
ll Pow(ll a,ll b){
	ll rec=1;
	for(;b;b>>=1,a=a*a%mod)
		if(b&1)rec=rec*a%mod;
	return rec;
}
ull rd(ull &x){
	x^=(x<<13);
	x^=(x>>7);
	x^=(x<<17);
	return x;
}
nade ppow(nade a,int b){
	nade c;c.init();
	for(;b;b>>=1,a=a*a)
		if(b&1)c=c*a;
	return c;
}
int main(){
	freopen("noodle.in","r",stdin);
	freopen("noodle.out","w",stdout);
	int test,T;ull seed;ll inv2=Pow(2,mod-2);
	scanf("%d%d%llu",&test,&T,&seed);
	for(int Case=1;Case<=T;Case++){
		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", &a[i]);
		if(k_max<=10){
			for(int i=1;i<=n;i++)val[0][i]=a[i];
			for(int i=1;i<=k_max;i++)
				for(int j=1;j<=n/2;j++)
					val[i][j*2-1]=val[i][j*2]=(val[i-1][j]+val[i-1][n-j+1])%mod;ll ans=0;
			for(int i=1;i<=q;i++){
				long long k=rd(seed)%k_max;
				ans=ans^(val[k][x]*Pow(inv2,k)%mod*i);
			}
			printf("%lld\n",ans);
			continue;
		}
		if(n<=500&&q<=500&&k_max<=500){
			vector<vector<int> >val(k_max+1);
			val[0].resize(n+1);
			for(int i=1;i<=n;i++)val[0][i]=a[i];
			for(int i=1;i<=k_max;i++){
				val[i].resize(n+1);
				for(int j=1;j<=n/2;j++)
					val[i][j*2-1]=val[i][j*2]=(val[i-1][j]+val[i-1][n-j+1])%mod;
			}ll ans=0;
			for(int i=1;i<=q;i++){
				long long k=rd(seed)%k_max;  
				ans=ans^(val[k][x]*Pow(inv2,k)%mod*i);
			}
			printf("%lld\n",ans);
			val.clear();
			continue;
		}
		if(n<=50&&q<=50){
			ll ans=0;nade st;
			for(int i=1;i<=n/2;i++)st.a[i][i*2]=st.a[i][i*2-1]=st.a[n-i+1][i*2]=st.a[n-i+1][i*2-1]=1;
			nade rec;
			for(int i=1;i<=n;i++)rec.a[1][i]=a[i];
			for(int i=1;i<=q;i++){
				long long k=rd(seed)%k_max;
				ans=(ans^((rec*ppow(st,k)).a[1][x]*Pow(inv2,k)%mod)*i);
			}
			printf("%lld\n",ans);
			continue;
		}
		int w=0;bool flag=false;
		for(;(1<<w)<=n;w++)
			if(n==(1<<w)){flag=true;break;}
		if(flag){
			ll sum=0;
			for(int i=1;i<=n;i++)sum=(sum+a[i])%mod;
			for(int i=1;i<=n;i++)val[0][i]=a[i];
			for(int i=1;i<w;i++)
				for(int j=1;j<=n/2;j++)
					val[i][j*2-1]=val[i][j*2]=(val[i-1][j]+val[i-1][n-j+1])%mod;
			ll ans=0;
			for(int i=1;i<=q;i++){
				long long k=rd(seed)%k_max;
				if(k<w)ans=ans^(val[k][x]*Pow(inv2,k)%mod*i);
				else{ans=ans^(sum*Pow(inv2,w)%mod*i);}
			}
			printf("%lld\n",ans);
			continue;
		}
	}
}
