#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
unsigned long long rd(unsigned long long &x){
	x ^= (x << 13);
	x ^= (x >> 7);
	x ^= (x << 17);
	return x;
}
const int N=2e6+5,TT=998244353,inv2=(TT+1)/2;
LL QSM(LL x,LL y){
	LL s=1;
	while(y){
		if(y&1) s=s*x%TT;
		x=x*x%TT,y>>=1;
	}
	return s;
}
int test,T;unsigned long long seed;
LL a[N],b[N];int n,q,x;LL k_max,ans;
namespace Cas1{
	LL p[11][N];
	void work(){
		for(int i=1;i<=n;i++) p[0][i]=a[i];
		for(int j=1;j<=k_max;j++)
		for(int i=1;i<=n;i++) p[j][i]=(p[j-1][(i+1)/2]+p[j-1][n-(i+1)/2+1])*inv2%TT;
		for(int i=1;i<=q;i++){
			LL k=rd(seed)%k_max;
			ans^=p[k][x]*i;
		}
		printf("%lld\n",ans);
	}
}
namespace Cas2{
	LL p[505][505];
	void work(){
		for(int i=1;i<=n;i++) p[0][i]=a[i];
		for(int j=1;j<=k_max;j++)
		for(int i=1;i<=n;i++) p[j][i]=(p[j-1][(i+1)/2]+p[j-1][n-(i+1)/2+1])*inv2%TT;
		for(int i=1;i<=q;i++){
			LL k=rd(seed)%k_max;
			ans^=p[k][x]*i;
		}
		printf("%lld\n",ans);
	}
}
namespace Cas3{
	LL p[N];
	struct Node{
		LL k;int id;
		bool operator <(const Node b)const{return k<b.k;}
	}A[N];
	void work(){
		for(int i=1;i<=q;i++){
			A[i].k=rd(seed)%k_max;
			A[i].id=i;
		}
		int now=0;LL sum=0;
		for(int i=1;i<=n;i++) sum=(sum+a[i])%TT;sum=sum*QSM(n,TT-2);
		sort(A+1,A+1+q);
		for(int i=1;i<=q;i++){
			LL k=A[i].k;
			if(k>30||(1ll<<k)>n){
				ans^=sum*A[i].id;
				continue;
			}
			while(now<k){
				for(int i=1;i<=n;i++) 
				p[i]=(a[i]+a[n-i+1])*inv2%TT;
				memcpy(a,p,sizeof p);now++;
			}
			ans^=a[(x-1)/(1<<now)+1]*A[i].id;
		}
		printf("%lld\n",ans);
	}
}
int main(){
	freopen("noodle.in","r",stdin);
	freopen("noodle1.out","w",stdout);
	scanf("%d%d%llu",&test,&T,&seed);
	for(int Case=1;Case<=T;Case++){
		scanf("%d%d%d%lld",&n,&q,&x,&k_max);ans=0;
		for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
//		if(k_max<=10){Cas1::work();continue;}
//		if(n<=500&&k_max<=500){Cas2::work();continue;}
		Cas3::work();
	}
	return 0;
}
