#include<bits/stdc++.h>
using namespace std;
inline long long read(){
	long long x=0,f=1;char ch=getchar();
	while ((ch!='-')&&(!isdigit(ch))) ch=getchar();
	if (ch=='-') f=-1;
	while (isdigit(ch)) x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
	return x*f;
}

	int Casing,Testing;
unsigned long long seed;
long long tn,A[2001010],teml,temr,Le[2001010],Ri[2001010],Va,K,V1,V2,bel[2001010],subb[2001010],Rem[2001010],subtag[2001010],KK,ans,inv2,k,now,cas,MOD,n,Q,X,finalans,kmax,b[62][170][170],i,j,c[1010][1010],a[2001010],d[1010][1010];
long long pow(long long x,long long y,long long p){
	long long ans=1;
	for (;y;y>>=1,x=x*x % p) if (y&1) ans=ans*x % p;
	return ans;
}
unsigned long long rd(unsigned long long &x){
	x^=(x<<13);
	x^=(x>>7);
	x^=(x<<17);
	return x;
}

void Subtask1(){
	n=read();Q=read();X=read();kmax=read();
	for (i=1;i<=n;i++) a[i]=read();
	subtag[0]=a[X];
	for (K=1;K<=kmax;K++){
		for (i=1;i<=n;i++) subb[i]=(a[(i+1)/2]+a[n-(i+1)/2+1])*inv2 % MOD;
		for (i=1;i<=n;i++) a[i]=subb[i];
		subtag[K]=a[X];
	}finalans=0;
	for (cas=1;cas<=Q;cas++){
		K=rd(seed) % kmax;
		finalans=finalans^(subtag[K]*cas);
	}
	printf("%lld\n",finalans);
}
void Subtask2(){
	n=read();Q=read();X=read();kmax=read();
	for (i=1;i<=n;i++) a[i]=read();finalans=0;
	for (k=0;k<=60;k++) for (i=1;i<=n;i++) for (j=1;j<=n;j++) b[k][i][j]=0;
	for (i=1;i<=n;i++) b[0][(i+1)/2][i]=1,b[0][n-(i+1)/2+1][i]=1;
	for (now=1;now<=60;now++)
		for (k=1;k<=n;k++)
		   for (i=1;i<=n;i++)
		      for (j=1;j<=n;j++)
		          b[now][i][j]=(b[now][i][j]+b[now-1][i][k]*b[now-1][k][j]) % MOD;
	for (cas=1;cas<=Q;cas++){
		   KK=rd(seed) % kmax;
		   for (i=1;i<=n;i++)
		      for (j=1;j<=n;j++)
		         c[i][j]=0;
		    for (i=1;i<=n;i++) c[i][i]=1;
		   for (now=0;now<=60;now++)
		       if (KK&(1ll<<now))
		           {
		           	for (i=1;i<=n;i++) d[i][X]=0;
		           	for (k=1;k<=n;k++)
		           	   for (i=1;i<=n;i++)
		           	           d[i][X]=(d[i][X]+b[now][i][k]*c[k][X]) % MOD;
		           	for (i=1;i<=n;i++)
		           	       c[i][X]=d[i][X];
				   }
			ans=0;
		  for (i=1;i<=n;i++)
		    ans=(ans+c[i][X]*a[i]) % MOD;
	      ans=ans*pow(inv2,KK,MOD) % MOD;
	      finalans=finalans^(ans*cas);
	}
	printf("%lld\n",finalans);
	return ;
}
void Subtask4(){
	for (i=1;i<=n;i++) a[i]=read();
	subtag[0]=a[X];
	for (K=1;K<=Va;K++){
		for (i=1;i<=n;i++) subb[i]=(a[(i+1)/2]+a[n-(i+1)/2+1])*inv2 % MOD;
		for (i=1;i<=n;i++) a[i]=subb[i];
		subtag[K]=a[X];
	}
	finalans=0;
	for (cas=1;cas<=Q;cas++){
		K=rd(seed) % kmax;
		if (K<=Va) finalans^=(subtag[K]*cas);
		else {
			finalans^=(subtag[Va]*cas);
		}
	}
	printf("%lld\n",finalans);
}
void Main(){
	if (Casing<=2){
		Subtask1();
		return ;
	}
	if ((Casing>=4)&&(Casing<=6)) 
	    {
		Subtask2();return ;
	    }
	n=read();Q=read();X=read();kmax=read();Va=0;
	for (i=60;i>=1;i--)
	    if ((n % (1ll<<i))==0)
	         {
	         	 Va=i;break;
			 }
	if ((1ll<<Va)==n) 
	    {
		Subtask4();
		return ;
	    }
	V1=(1ll<<Va);V2=V1<<1;
	for (i=1;i<=n-V1;i++) 
	    {
		bel[i]=(i-1)/V2+1,Rem[bel[i]]=i;
	    }
	for (i=n-V1+1;i<=n;i++) bel[i]=bel[n-V1]+1,Rem[bel[i]]=i;
	for (i=1;i<=n;i++){
		teml=(i+1)/2;temr=n-teml+1;
	    Le[bel[i]]=bel[teml];Ri[bel[i]]=bel[temr];
	}
	for (i=1;i<=n;i++) a[i]=read();
	subtag[0]=a[X];
	for (K=1;K<=Va+1;K++){
		for (i=1;i<=n;i++) subb[i]=(a[(i+1)/2]+a[n-(i+1)/2+1]) % MOD;
		for (i=1;i<=n;i++) a[i]=subb[i];
		subtag[K]=a[X]*pow(inv2,K,MOD) % MOD;
	}tn=bel[n];
	for (i=1;i<=tn;i++) A[i]=a[Rem[i]];
	finalans=0;
	for (now=0;now<=60;now++) for (i=1;i<=tn;i++) for (j=1;j<=tn;j++) b[now][i][j]=0;
	for (i=1;i<=tn;i++) b[0][Le[i]][i]++,b[0][Ri[i]][i]++;
	for (now=1;now<=60;now++) 
	   for (k=1;k<=tn;k++)
	       for (i=1;i<=tn;i++)
	          for (j=1;j<=tn;j++)
	              b[now][i][j]=(b[now][i][j]+b[now-1][i][k]*b[now-1][k][j]) % MOD;
	for (cas=1;cas<=Q;cas++){
		   KK=rd(seed) % kmax;
		   if (KK<=Va+1) {finalans^=(subtag[KK]*cas);continue;}
		   KK-=(Va+1);
		   for (i=1;i<=tn;i++)
		      for (j=1;j<=tn;j++)
		         c[i][j]=0;
		    for (i=1;i<=tn;i++) c[i][i]=1;
		   for (now=0;now<=60;now++)
		       if (KK&(1ll<<now))
		           {
		           	for (i=1;i<=tn;i++) d[i][bel[X]]=0;
		           	for (k=1;k<=tn;k++)
		           	   for (i=1;i<=tn;i++)
		           	           d[i][bel[X]]=(d[i][bel[X]]+b[now][i][k]*c[k][bel[X]]) % MOD;
		           	for (i=1;i<=tn;i++)
		           	       c[i][bel[X]]=d[i][bel[X]];
				   }
			ans=0;
		  for (i=1;i<=tn;i++)
		    ans=(ans+c[i][bel[X]]*A[i]) % MOD;
	      ans=ans*pow(inv2,KK+Va+1,MOD) % MOD;
	      finalans=finalans^(ans*cas);
	}
	printf("%lld\n",finalans);
}
int main(){
	freopen("noodle.in","r",stdin);
	freopen("noodle.out","w",stdout);
	scanf("%d%d%llu",&Casing,&Testing,&seed);MOD=998244353;
	inv2=(MOD+1)/2;
	for (;Testing;Testing--) Main();
	return 0;
}

