#include <bits/stdc++.h>
using namespace std;

#define Mod(x) (x>=P)&&(x-=P)
#define rep(i,a,b) for(int i=a,i##end=b;i<=i##end;++i)
#define drep(i,a,b) for(int i=a,i##end=b;i>=i##end;--i)
#define erep(i,a) for(int i=hd[a],y;y=to[i],i;i=nxt[i])

typedef long long ll;
void Max(int &x,int y){x<y&&(x=y);}
void Min(int &x,int y){x>y&&(x=y);}

bool f1;
const int M=2e6+10,P=998244353,inv_2=(P+1)/2;
int A[M];
bool f2;

unsigned long long rd(unsigned long long &x) {
	x ^= (x << 13);
	x ^= (x >> 7);
	x ^= (x << 17);
	return x;
}

int n,q,x;
unsigned long long sed;
long long k_max;
namespace P10{
	int B[M];
	int res[M];
	void solve(){
		ll ans=0;
		rep(i,1,n)B[i]=A[i];
		res[0]=B[x];
		rep(i,1,k_max){
			rep(j,1,n/2)B[j]+=B[n-j+1],Mod(B[j]);
			drep(j,n,1)B[j]=1ll*B[(j+1)/2]*inv_2%P;
			res[i]=B[x];
		}
		rep(p,1,q){
			ll k = rd(sed) % k_max;
			ans=ans^(1ll*res[k]*p);
		}
		printf("%lld\n",ans);
	}
}
namespace P15{
	int B[M];
	int res[M];
	void solve(){
		ll ans=0;
		rep(i,1,n)B[i]=A[i];
		res[0]=B[x];
		rep(i,1,min(25ll,k_max)){
			rep(j,1,n/2)B[j]+=B[n-j+1],Mod(B[j]);
			drep(j,n,1)B[j]=1ll*B[(j+1)/2]*inv_2%P;
			res[i]=B[x];
		}
		rep(p,1,q){
			ll k = rd(sed) % k_max;
			ans=ans^(1ll*res[min(25ll,k)]*p);
		}
		printf("%lld\n",ans);
	}
}
namespace P30{
	int f[62][155][155],res[2][155];
	void solve(){
		memset(f,0,sizeof f);
		rep(i,1,n){
			int t=(i+1)/2;
			f[0][i][t]=inv_2;
			f[0][i][n-t+1]=inv_2;
		}
		rep(p,1,60)rep(k,1,n)rep(i,1,n)rep(j,1,n)
			f[p][i][j]=(f[p][i][j]+1ll*f[p-1][i][k]*f[p-1][k][j])%P;
		ll ans=0;
		rep(p,1,q){
			ll k = rd(sed) % k_max;
			memset(res,0,sizeof res);
			res[0][x]=1;
			drep(l,60,0)if(1ll<<l&k){
				rep(i,1,n)rep(j,1,n)
					res[1][j]=(res[1][j]+1ll*res[0][i]*f[l][i][j])%P;
				memcpy(res[0],res[1],sizeof res[1]);
				memset(res[1],0,sizeof res[1]);
			}
			int tmp=0;
			rep(i,1,n)tmp=(tmp+1ll*res[0][i]*A[i])%P;
			ans=ans^(1ll*tmp*p);
		}
		printf("%lld\n",ans);
	}
}
namespace P35{
	int B[M],f[66][5][5];
	int tt[2][5];
	int res[M];
	void solve(){
		ll ans=0;
		rep(i,1,n)B[i]=A[i];
		res[0]=B[x];
		rep(i,1,min(25ll,k_max)){
			rep(j,1,n/2)B[j]+=B[n-j+1],Mod(B[j]);
			drep(j,n,1)B[j]=1ll*B[(j+1)/2]*inv_2%P;
			res[i]=B[x];
		}
		int op;
		if(x<=n/3)op=1;
		else if(x<=n/3*2)op=2;
		else op=3;
		f[0][3][1]=f[0][1][1]=inv_2;
		f[0][3][2]=f[0][1][2]=inv_2;
		f[0][2][3]=1;
		rep(p,1,60)rep(k,1,3)rep(i,1,3)rep(j,1,3)
			f[p][i][j]=(f[p][i][j]+1ll*f[p-1][i][k]*f[p-1][k][j])%P;
		rep(p,1,q){
			ll k = rd(sed) % k_max;
			if(k<=25)ans=ans^(1ll*res[min(25ll,k)]*p);
			else {
				int stp=k-25;
				tt[0][1]=B[1],tt[0][2]=B[n/3+1],tt[0][3]=B[n];
				rep(l,0,60)if(1ll<<l&stp){
					rep(i,1,3)rep(j,1,3)
						tt[1][j]=(tt[1][j]+1ll*tt[0][i]*f[l][i][j])%P;
					memcpy(tt[0],tt[1],sizeof tt[1]);
					memset(tt[1],0,sizeof tt[1]);
				}
				ans=ans^(1ll*tt[0][op]*p);
			}
		}
		printf("%lld\n",ans);
	}
}
int main() {
	cerr<<(&f1-&f2)/1024.0/1024<<endl;
	freopen("noodle.in","r",stdin);
	freopen("noodle.out","w",stdout);
	int test, T;
	scanf("%d%d%llu", &test, &T, &sed);
	for(int Case = 1; Case <= T; Case ++) {
		scanf("%d%d%d%lld", &n, &q, &x, &k_max);
		rep(i,1,n)scanf("%d",&A[i]);
		if(test<=2)P10::solve();
		else if(test==3)P15::solve();
		else if(test<=6)P30::solve();
		else if(test==7)P35::solve();
	}
	return 0;
}
