#include<bits/stdc++.h>
#define mod 998244353
#define inv 499122177
using namespace std;
int n,q,x,test,a[2000005],b[24][2000005],c[3000][3000];
long long m;
unsigned long long seed;
unsigned long long rd(unsigned long long &x)
{
	x^=(x<<13);
	x^=(x>>7);
	x^=(x<<17);
	return x;
}
int kp(int a,int b)
{
	int c=1;
	while(b)
	{
		if(b&1) c=1ll*a*c%mod;
		a=1ll*a*a%mod;
		b>>=1;
	}
	return c;
}
int phi(int x)
{
	int ans=1;
	for(int i=2;i*i<=x;i++)
		if(x%i==0)
		{
			ans*=i-1;
			x/=i;
			while(x%i==0) x/=i,ans*=i;
		}
	if(x>1) ans*=x-1;
	return ans;
}
int mo(int x)
{
	return x>=mod?x-mod:x;
}
void solve()
{
	long long ans=0;
	scanf("%d%d%d%lld",&n,&q,&x,&m);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	if(test<=2)
	{
		for(int i=1;i<=n;i++) b[0][i]=a[i];
		for(int i=1;i<m;i++)
		{
			for(int j=1;j<=(n>>1);j++) b[i][j]=mo(b[i-1][j]+b[i-1][n-j+1]);
			for(int j=n;j;j--) b[i][j]=1ll*inv*b[i][(j+1)>>1]%mod;
		}
		for(int i=1;i<=q;i++)
		{
			long long k=rd(seed)%m;
			ans^=1ll*b[k][x]*i;
		}
		printf("%lld\n",ans);
		return;
	}
	int _n=n;
	int m1=1;
	while(!(_n&1)) _n>>=1,++m1;
	for(int i=1;i<=n;i++) b[0][i]=a[i];
	for(int i=1;i<=m1;i++)
	{
		for(int j=1;j<=(n>>1);j++) b[i][j]=mo(b[i-1][j]+b[i-1][n-j+1]);
		for(int j=n;j;j--) b[i][j]=b[i][(j+1)>>1];
	}
	int __n=_n;
	_n=phi(_n);
	for(int i=1;i<=__n;i++) c[0][i]=b[m1][i*(n/__n)];
	for(int i=1;i<=_n;i++)
	{
		for(int j=1;j<=(__n>>1);j++) c[i][j]=mo(c[i-1][j]+c[i-1][__n-j+1]);
		for(int j=__n;j;j--) c[i][j]=c[i][(j+1)>>1];
	}
	int invn=kp(__n,mod-2);
	for(int i=1;i<=q;i++)
	{
		long long k=rd(seed)%m;
		if(k<=m1) ans^=1ll*b[k][x]*kp(inv,k)%mod*i;
		else
		{
			k-=m1;
			int p=(k-1)%_n+1,sum=kp(2,k)-kp(2,p)+mod;
			sum=1ll*sum*invn%mod;
			int an=c[p][x];
			for(int i=1;i<=__n;i++) an=(an+1ll*sum*b[m1][i*(n/__n)]%mod*(n/__n)%mod)%mod;
			ans^=1ll*an*i;
		}
	}
	printf("%lld\n",ans);
}
int main()
{
	freopen("noodle.in","r",stdin);
	freopen("noodle.out","w",stdout);
	int t;
	scanf("%d%d%llu",&test,&t,&seed);
	while(t)
	{
		--t;
		solve();
	}
	return 0;
}
