#include<bits/stdc++.h>
#include<bits/extc++.h>
using namespace std;
#define cst const
#define il inline
#define fir first
#define gc getchar
#define pc putchar
#define ret return
#define sec second
#define ll long long
#define tmpl template
#define db long double
#define pr pair<ll,ll>
#define prpr make_pair
#define ull unsigned ll
#define uint unsigned int
#define file(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)
cst ll HgS=998244353,inf=0x3f3f3f3f3f3f3f3fll,neinf=0xc0c0c0c0c0c0c0c0ll;
tmpl<class T=ll>il T rd()
{
	T res=0;int lab=1,ch=gc();
	while((ch<'0'||ch>'9')&&ch!=EOF)lab^=(ch=='-'),ch=gc();
	if(ch==EOF)ret -1926;
	while(ch>='0'&&ch<='9')res=res*10+(ch&15),ch=gc();
	ret lab?res:-res;
}
tmpl<class T=ll>il void prt(T x,char tail='\n')
{
	static int s[75];int t=0;
	if(x<0)x=-x,pc('-');
	do{T tmp=x/10;s[++t]=x-tmp*10;x=tmp;}while(x);
	while(t)pc(s[t--]|48);
	if(tail)pc(tail);
}
ull rnd(ull&x)
{
	x^=(x<<13);
	x^=(x>>7);
	x^=(x<<17);
	return x;
}
cst ll V=1000000;
il ll qpow(ll n,ll e,ll p)
{n%=p;ll res=1;while(e){(e&1)&&(res=res*n%p),n=n*n%p;e>>=1;}ret res;}
int a[21][V+5],b[V+5],pw[3][V+5],pi[3][V+5],npw[3][V+5],n,q,x,d1,d2,invn;cst ll inv2=(HgS+1)>>1;
ll k_max;ull seed;
il ll lowbit(ll x){ret x&(-x);}
il ll mpow(ll e)
{
	ll b=e/V,c=b/V;e-=b*V;b-=c*V;
	ret 1ll*pw[2][c]*pw[1][b]%HgS*pw[0][e]%HgS;
}
il ll mpoi(ll e)
{
	ll b=e/V,c=b/V;e-=b*V;b-=c*V;
	ret 1ll*pi[2][c]*pi[1][b]%HgS*pi[0][e]%HgS;
}
il ll npow(ll e)
{
	ll b=e/V,c=b/V;e-=b*V;b-=c*V;
	ret 1ll*npw[2][c]*npw[1][b]%n*npw[0][e]%n;
}
il ll fun(int t,ll k)
{
	ll b=t*npow(k-1)%n,a=(t*mpow(k-1)%HgS-b+HgS)*invn%HgS;
	ret (2*a+(b>=d1)+(b>=d2))%HgS;
}
int main()
{
	file("noodle");
	int test,T;scanf("%d%d%llu",&test,&T,&seed);
	//cerr<<"T"<<endl;
	for(int i=0;i<3;++i)pw[i][0]=pi[i][0]=1;
	pw[0][1]=2;pi[0][1]=inv2;
	for(int i=2;i<=V;++i)pw[0][i]=1ll*pw[0][i-1]*pw[0][1]%HgS;
	for(int i=2;i<=V;++i)pi[0][i]=1ll*pi[0][i-1]*pi[0][1]%HgS;
	pw[1][1]=pw[0][V];pi[1][1]=pi[0][V];
	for(int i=2;i<=V;++i)pw[1][i]=1ll*pw[1][i-1]*pw[1][1]%HgS;
	for(int i=2;i<=V;++i)pi[1][i]=1ll*pi[1][i-1]*pi[1][1]%HgS;
	pw[2][1]=pw[1][V];pi[2][1]=pi[1][V];
	for(int i=2;i<=V;++i)pw[2][i]=1ll*pw[2][i-1]*pw[2][1]%HgS;
	for(int i=2;i<=V;++i)pi[2][i]=1ll*pi[2][i-1]*pi[2][1]%HgS;
	//cerr<<"T"<<endl;
	for(int Case=1;Case<=T;Case++)
	{
		n=rd(),q=rd(),x=rd(),k_max=rd();invn=qpow(n,HgS-2,HgS);ll ans=0;
		//cerr<<"T"<<endl;
		for(int i=0;i<3;++i)npw[i][0]=1;
		npw[0][1]=2;
		for(int i=2;i<=V;++i)npw[0][i]=1ll*npw[0][i-1]*npw[0][1]%n;
		npw[1][1]=npw[0][V];
		for(int i=2;i<=V;++i)npw[1][i]=1ll*npw[1][i-1]*npw[1][1]%n;
		npw[2][1]=npw[1][V];
		for(int i=2;i<=V;++i)npw[2][i]=1ll*npw[2][i-1]*npw[2][1]%n;
		//cerr<<"T"<<endl;
		for(int i=1;i<=n;i++)b[i]=a[0][i]=rd();
		for(int i=n-1;i>=1;--i)b[i]=(b[i]-a[0][i+1]+HgS)%HgS;
		//cerr<<"T"<<endl;
		for(int k=1;k<=20;++k)
		{
			for(int i=1,j=n;i<=j;++i,--j)a[k][i]=a[k-1][i]+a[k-1][j];
			for(int i=n;i>=1;i-=2)
			{
				int val=inv2*a[k][i>>1]%HgS;
				a[k][i-1]=a[k][i]=val;
			}
		}
		//cerr<<"T"<<endl;
		for(int i=1;i<=q;i++)
		{
			ll k=rnd(seed)%k_max;
			if(k>20)
			{
				ll res=0;d1=(x+1)>>1,d2=n+1-d1;
				for(int i=1;i<=n;++i)res=(res+a[0][i]*(fun(i,k)-fun(i-1,k)+HgS))%HgS;
				res=res*mpoi(k)%HgS;ans^=i*res;//cerr<<k<<' '<<res<<endl;
			}
			else ans^=1ll*i*a[k][x];
		}
		//cerr<<"T"<<endl;
		prt(ans);
	}
	ret 0;
}