#include<bits/stdc++.h>
using namespace std;
#define O 998244353
#define iv2 499122177ll
int test,T,n,q,X;
long long K;
int seq[2000005];
#define gc getchar
inline void Read(int &s){
	char ch=gc();s=0;
	while(ch<'0'||ch>'9')ch=gc();
	while(ch>='0'&&ch<='9')
	s=(ch&15)+(s<<1)+(s<<3),ch=gc();
}
inline void Read(long long &s){
	char ch=gc();s=0;
	while(ch<'0'||ch>'9')ch=gc();
	while(ch>='0'&&ch<='9')
	s=(ch&15)+(s<<1)+(s<<3),ch=gc();
}
#undef gc
unsigned long long seed;
unsigned long long rd (unsigned long long &x ) {
	x ^= ( x << 13 ) ;
	x ^= ( x >> 7 ) ;
	x ^= ( x << 17 ) ;
	return x ;
}
namespace test1{
	int B[505],F[505];
	void Pre(){
		for(int i=1;i<=n;i++)B[i]=seq[i];
		F[0]=B[X];
		for(int i=1;i<=K;i++){
			for(int j=1;j*2<=n;j++)
			(B[j]+=B[n-j+1])%=O,B[j]=iv2*B[j]%O;
			for(int j=n/2;j>=1;j--)
			B[j*2]=B[j*2-1]=B[j];
			F[i]=B[X];
		}
	}
	void Main(){
		while(T--){
			Read(n);Read(q);Read(X);Read(K);
			for(int i=1;i<=n;i++)Read(seq[i]);
			Pre();long long Ans=0;
			for(int qi=1;qi<=q;qi++){
				long long k=rd(seed)%K;
//				long long k=qi;
				Ans^=1ll*qi*F[k];
//				cout<<F[k]<<'\n';
			}
			cout<<Ans<<'\n';
		}
	}
}
namespace test2{
	int B[2000005],F[15];
	void Pre(){
		for(int i=1;i<=n;i++)B[i]=seq[i];
		F[0]=B[X];
		for(int i=1;i<=K;i++){
			for(int j=1;j*2<=n;j++)
			(B[j]+=B[n-j+1])%=O,B[j]=iv2*B[j]%O;
			for(int j=n/2;j>=1;j--)
			B[j*2]=B[j*2-1]=B[j];
			F[i]=B[X];
		}
	}
	void Main(){
		while(T--){
			Read(n);Read(q);Read(X);Read(K);
			for(int i=1;i<=n;i++)Read(seq[i]);
			Pre();long long Ans=0;
			for(int qi=1;qi<=q;qi++){
				long long k=rd(seed)%K;
				Ans^=1ll*qi*F[k];
			}
			cout<<Ans<<'\n';
		}
	}
}
namespace test3{
	int B[2000005],F[25],KG;
	void Pre(){
		for(int i=1;i<=n;i++)B[i]=seq[i];
		while((1<<KG)<n)++KG;F[0]=B[X];
		for(int i=1;i<=KG;i++){
			for(int j=1;j*2<=n;j++)
			(B[j]+=B[n-j+1])%=O,B[j]=iv2*B[j]%O;
			for(int j=n/2;j>=1;j--)
			B[j*2]=B[j*2-1]=B[j];
			F[i]=B[X];
		}
	}
	void Main(){
		while(T--){
			Read(n);Read(q);Read(X);Read(K);
			for(int i=1;i<=n;i++)Read(seq[i]);
			Pre();long long Ans=0;
			for(int qi=1;qi<=q;qi++){
				long long k=rd(seed)%K;
				Ans^=1ll*qi*F[(k>KG?KG:k)];
			}
			cout<<Ans<<'\n';
		}
	}
}
namespace test7{
	struct MAT{
		int A[4];
		MAT operator * (const MAT &u)const{
			return (MAT){
				{
				(1ll*A[0]*u.A[0]%O+1ll*A[1]*u.A[2]%O)%O,
				(1ll*A[0]*u.A[1]%O+1ll*A[1]*u.A[3]%O)%O,
				(1ll*A[2]*u.A[0]%O+1ll*A[3]*u.A[2]%O)%O,
				(1ll*A[2]*u.A[1]%O+1ll*A[3]*u.A[3]%O)%O
				}
			};
		}
	}uni,TA;
	MAT Mpow(MAT ds,long long ix){
		MAT re=uni;while(ix){
			if(ix&1)re=re*ds;
			ix>>=1;ds=ds*ds;
		}return re;
	}
	int B[2000005],F[20],a0,b0,LG;
	void Pre(){
		while((1<<LG)<(n&-n))++LG;
		for(int i=1;i<=n;i++)B[i]=seq[i];
		F[0]=B[X];
		for(int i=1;i<=LG+1;i++){
			for(int j=1;j*2<=n;j++)
			(B[j]+=B[n-j+1])%=O,B[j]=iv2*B[j]%O;
			for(int j=n/2;j>=1;j--)
			B[j*2]=B[j*2-1]=B[j];
			F[i]=B[X];a0=B[1];b0=B[n];
		}
	}
	void Main(){
		uni=(MAT){{1,0,0,1}};
		TA=(MAT){{0,iv2,1,iv2}};
		while(T--){
			Read(n);Read(q);Read(X);Read(K);
			for(int i=1;i<=n;i++)Read(seq[i]);
			Pre();long long Ans=0;
			for(int qi=1;qi<=q;qi++){
				long long k=rd(seed)%K;
//				long long k=qi;
				if(qi>=3)
				int skdj=0;
				if(k<=LG+1){
					Ans^=1ll*qi*F[k];
//					cout<<F[k]<<'\n';
					continue;
				}
				MAT tmp=Mpow(TA,k-LG-1);
				if(X>(1<<(LG+1))){
					int ans=1ll*a0*tmp.A[2]%O+1ll*b0*tmp.A[0]%O;
					ans%=O;Ans^=1ll*qi*ans;//cout<<ans<<'\n';
				}else{
					int ans=1ll*a0*tmp.A[3]%O+1ll*b0*tmp.A[1]%O;
					ans%=O;Ans^=1ll*qi*ans;//cout<<ans<<'\n';
				}
			}
			cout<<Ans<<'\n';
		}
	}
}
inline long long qkpw(int ds,int ix){
	long long re=1;while(ix){
		if(ix&1)re=1ll*re*ds%O;
		ix>>=1;ds=1ll*ds*ds%O;
	}return re;
}
namespace test4{
	struct MAT{
		int A[55][55];
		void clear(){memset(A,0,sizeof(A));}
		MAT operator * (const MAT &u)const{
			MAT tmp;
			for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++)
			tmp.A[i][j]=0;
			for(int i=1;i<=n;i++)
			for(int k=1;k<=n;k++)
			for(int j=1;j<=n;j++){
				(tmp.A[i][j]+=1ll*A[i][k]*u.A[k][j]%O)%=O;
			}
			return tmp;
		}
		
	}uni,TA;
	void Pre(){
		uni.clear();TA.clear();
		for(int i=1;i<=n;i++)uni.A[i][i]=1;
		for(int j=1;j<=n;j++){
			TA.A[(j+1)/2][j]=iv2;
			TA.A[n-(j+1)/2+1][j]=iv2;
		}
	}
	MAT Mpow(MAT ds,long long ix){
		MAT re=uni;while(ix){
			if(ix&1)re=re*ds;
			ix>>=1;ds=ds*ds;
		}return re;
	}
	MAT Tpow;
	int B[55];
	void MUL(){
		for(int i=1;i<=n;i++)B[i]=0;
		for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
		(B[j]+=1ll*seq[i]*Tpow.A[i][j]%O)%=O;
	}
	void Main(){
		while(T--){
			Read(n);Read(q);Read(X);Read(K);
			for(int i=1;i<=n;i++)Read(seq[i]);
			Pre();long long Ans=0;
			for(int qi=1;qi<=q;qi++){
				long long k=rd(seed)%K;
				Tpow=Mpow(TA,k);MUL();
				Ans^=1ll*qi*B[X];
//				cout<<B[X]<<'\n';
			}
			cout<<Ans<<'\n';
		}
		
	}
}
namespace test5{
	struct MAT{
		int A[155][155];
		void clear(){for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)A[i][j]=0;}
		MAT operator * (const MAT &u)const{
			MAT tmp;
			for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++)
			tmp.A[i][j]=0;
			for(int i=1;i<=n;i++)
			for(int k=1;k<=n;k++)
			for(int j=1;j<=n;j++){
				(tmp.A[i][j]+=1ll*A[i][k]*u.A[k][j]%O)%=O;
			}
			return tmp;
		}
		
	}uni,TA;
	void Pre(){
		uni.clear();TA.clear();
		for(int i=1;i<=n;i++)uni.A[i][i]=1;
		for(int j=1;j<=n;j++){
			TA.A[(j+1)/2][j]=iv2;
			TA.A[n-(j+1)/2+1][j]=iv2;
		}
	}
	MAT Mpow(MAT ds,long long ix){
		MAT re=uni;while(ix){
			if(ix&1)re=re*ds;
			ix>>=1;ds=ds*ds;
		}return re;
	}
	MAT Tpow;
	int B[155];
	void MUL(){
		for(int i=1;i<=n;i++)B[i]=0;
		for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
		(B[j]+=1ll*seq[i]*Tpow.A[i][j]%O)%=O;
	}
	void Main(){
		while(T--){
			Read(n);Read(q);Read(X);Read(K);
			for(int i=1;i<=n;i++)Read(seq[i]);
			Pre();long long Ans=0;
			for(int qi=1;qi<=q;qi++){
				long long k=rd(seed)%K;
				Tpow=Mpow(TA,k);MUL();
				Ans^=1ll*qi*B[X];
//				cout<<B[X]<<'\n';
			}
			cout<<Ans<<'\n';
		}
		
	}
}
long long frac(int x,int y){
	return 1ll*x*qkpw(y,O-2)%O;
}
int main(){
	freopen("noodle.in","r",stdin);
	freopen("noodle.out","w",stdout);
	scanf("%d%d%llu",&test,&T,&seed);
	switch(test){
//		case 0:test5::Main();break;
		case 1:test1::Main();break;
		case 2:test2::Main();break;
		case 3:test3::Main();break;
		case 4:test4::Main();break;
		case 5:test5::Main();break;
		case 7:test7::Main();break;
	}
	return 0;
}
