#include<bits/stdc++.h>
#define pb push_back
using namespace std;
inline int read(){
	int x=0,f=1;
	char c=getchar();
	while(!isdigit(c)){
		if(c=='-') f=~f+1;c=getchar();
	}
	while(isdigit(c)){
		x=(x<<3)+(x<<1)+(c^48);
		c=getchar();
	}
	return f==-1?~x+1:x;
}
const int mod=998244353;

int qpow(int x,int k=mod-2){
	int res=1;
	while(k){
		if(k&1) res=1ll*res*x%mod;x=1ll*x*x%mod;k>>=1;
	}
	return res;
}
unsigned long long rd(unsigned long long &x) {
	x ^= (x << 13);
	x ^= (x >> 7);
	x ^= (x << 17);
	return x;
}
int n, q, x;
long long k_max;
int test, T;
unsigned long long seed;
int a[2000010];
struct matrix{
	unsigned long long a[510][510];
	matrix(){
		memset(a,0,sizeof(a));
	}
	void clea(){
		memset(a,0,sizeof(a));
	}
}Mat[75];
void addx(int &x,int y){
	(x+=y)>=mod?x-=mod:x;
}
matrix operator *(matrix x,matrix y){
	matrix ret;
	for(int i=1;i<=n;++i){
		for(int j=1;j<=n;++j){
			for(int k=1;k<=n;++k){
//				(ret.a[i][k]+=1ll*x.a[i][j]*y.a[j][k]%mod)%=mod;
				ret.a[i][k]+=x.a[i][j]*y.a[j][k];
				if(j==n||(j&8)==0) ret.a[i][k]%=mod;
			}
		}
	}
	return ret;
}
struct line{
	unsigned long long a[510];
	line(){
		memset(a,0,sizeof(a));
	}
};
line operator *(const line &x,const matrix &y){
	line ret;
	for(int i=1;i<=n;++i){
		for(int j=1;j<=n;++j){
//			(ret.a[j]+=1ll*x.a[i]*y.a[i][j]%mod)%=mod;
			ret.a[j]+=x.a[i]*y.a[i][j];
			if((i&8)==0||i==n) ret.a[j]%=mod;
		}
	}
	return ret;
}
int b[31][2000010];
void bruteforce(){
	long long ans=0;
	for(int i=1;i<=n;++i) b[0][i]=a[i];
	for(int i=1;i<=n;++i) for(int j=1;j<k_max;++j) b[j][i]=0;
	for(int i=1;i<k_max;++i){
		for(int j=1;j<=n;++j){
			int p=min(j,n-j+1);
			addx(b[i][(p<<1)-1],1ll*(mod+1>>1)*b[i-1][j]%mod);
			addx(b[i][p<<1],1ll*(mod+1>>1)*b[i-1][j]%mod);
		}
	}
	for(int i = 1; i <= q; i ++) {
		long long k = rd(seed) % k_max;
//		line res=o;
//		for(int j=0;j<64;++j) if(k>>j&1) res=res*Mat[j];
////		printf("%d\n",res.a[x]);
		ans^=(1ll*b[k][x]*i);
	}
	printf("%lld\n",ans);
}
int main() {
	freopen("noodle.in","r",stdin);
	freopen("noodle.out","w",stdout);
//	printf("are you ok\n");
	scanf("%d%d%llu", &test, &T, &seed);
	for(int Case = 1; Case <= T; Case ++) {
		scanf("%d%d%d%lld", &n, &q, &x, &k_max);
//		vector<int> a(n + 1);
		for(int i=1;i<=n;i++) a[i]=read();
		if(test==2||test==0){// O(nk)
			bruteforce();continue ;
		}
		if(test==3){// n = 2^k
			int mx=1;
			while((1<<mx)<n) mx++;
			for(int i=1;i<=n;++i) b[0][i]=a[i];
			for(int i=1;i<=n;++i) for(int j=1;j<mx;++j) b[j][i]=0;
			for(int i=1;i<mx;++i){
				for(int j=1;j<=n;++j){
					int p=min(j,n-j+1);
					addx(b[i][(p<<1)-1],1ll*(mod+1>>1)*b[i-1][j]%mod);
					addx(b[i][p<<1],1ll*(mod+1>>1)*b[i-1][j]%mod);
				}
			}
			int sum=0;
			for(int i=1;i<=n;++i) addx(sum,a[i]);
			sum=1ll*sum*qpow(n)%mod;
			long long ans=0;
			for(int i = 1; i <= q; i ++) {
				long long k = rd(seed) % k_max;
				if(k<mx) ans^=(1ll*b[k][x]*i);
				else ans^=(1ll*sum*i);
			}
			printf("%lld\n",ans);
			continue ;
		}// O (n^3logk+qn^2logk)
		line o;
		for(int i=1;i<=n;++i) o.a[i]=a[i];
		Mat[0].clea();
		for(int i=1;i<=n;++i){
			int p=min(i,n-i+1);
//			printf("i:%d,p:%d\n",i,p);
			Mat[0].a[i][(p<<1)-1]=Mat[0].a[i][p<<1]=(mod+1>>1);
		}
		for(int i=1;i<64;++i) Mat[i]=Mat[i-1]*Mat[i-1];
		long long ans=0;
		for(int i=1;i<=q;++i){
//			for(int j=1;j<=n;++j) printf("%d ",Mat[0].a[i][j]);printf("\n");
			long long k = rd(seed) % k_max;
			line res=o;
			for(int j=0;j<64;++j) if(k>>j&1) res=res*Mat[j];
//			printf("%d\n",res.a[x]);
			ans^=(1ll*res.a[x]*i);
		}
		printf("%lld\n",ans);
	}
}