#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long u64;
const int N=2e6+6,md=998244353;
int Tid,T,a[N];
u64 seed,K;
int n,m,pos;
inline int pow(int a,LL b){
	int res=1;
	for(;b;b>>=1,a=(LL)a*a%md)if(b&1)res=(LL)res*a%md;
	return res;
}
inline u64 getNxt(u64&x){
	x^=x<<13,x^=x>>7,x^=x<<17;
	return x;
}
inline void trans(){
	static int b[N];
	for(int i=1;i<=n/2;++i)b[i]=(a[i]+a[n-i+1])%md;
	for(int i=1;i<=n;++i)a[i]=b[(i+1)/2];
}
namespace sub1{
	int A[22];
	void work(){
		A[0]=a[pos];
		for(int t=1;t<22;++t){
			trans();
			A[t]=a[pos];
		}
		u64 ans=0;
		for(int i=1;i<=m;++i){
			LL x=getNxt(seed)%K;
			int y=pow((md+1)/2,x);
			if(x>21)x=21;
			ans^=(u64)A[x]*y%md*i;
		}
		cout<<ans<<'\n';
	}
}
int lim;
struct matrix{
	int A[128][128];
	inline matrix(){memset(A,0,sizeof A);}
	inline matrix operator*(const matrix&b)const{
		matrix c;
		for(int i=1;i<=lim;++i)
			for(int k=1;k<=lim;++k)
				for(int j=1;j<=lim;++j)
					c.A[i][j]=(c.A[i][j]+(LL)A[i][k]*b.A[k][j])%md;
		return c;
	}
	inline void trans(int*a){
		static int tmp[128];
		for(int i=1;i<=lim;++i)tmp[i]=0;
		for(int k=1;k<=lim;++k)
			for(int j=1;j<=lim;++j)
				tmp[j]=(tmp[j]+(LL)a[k]*A[k][j])%md;
		for(int i=1;i<=lim;++i)a[i]=tmp[i];
	}
};
namespace sub2{
	int rec[5],d[128];
	matrix B[60];
	void work(){
		for(int i=0;i<=3;++i){
			rec[i]=a[pos];
			trans();
		}
		lim=(n+3)/4;
		for(int i=1;i<=lim;++i)d[i]=a[i*4-3];
		matrix c;
		for(int i=1;i<=n;i+=4){
			int x=(i+1)/2;
			++c.A[(x+3)/4][i];
			x=n-x+1;
			++c.A[(x+3)/4][i];
		}
		B[0]=c;
		for(int i=1;i<60;++i)B[i]=B[i-1]*B[i-1];
		u64 ans=0;
		for(int i=1;i<=m;++i){
			LL x=getNxt(seed)%K;
			if(x<=3)ans^=(u64)rec[x]*pow((md+1)/2,x)%md*i;
			else{
				x-=4;
				static int g[128];
				memcpy(g,d,sizeof g);
				for(int w=59;~w;--w)if(x>>w&1)
					B[w].trans(g);
				ans^=(u64)g[(x+3)/4]*pow((md+1)/2,x+4)%md*i;
			}
		}
		cout<<ans<<'\n';
	}
}
int main(){
	freopen("noodle.in","r",stdin);
	freopen("answer.txt","w",stdout);
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>Tid>>T>>seed;
	while(T--){
		cin>>n>>m>>pos>>K;
		for(int i=1;i<=n;++i)cin>>a[i];
		if(K<=21||__builtin_popcount(n)==1)sub1::work();
		else if(n<=500&&m<=500)sub2::work();
	}
	return 0;
}
