#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define Rg register
#define RI Rg int
#define Cn const
#define CI Cn int&
#define I inline
#define W while
#define N 2000000
#define BN 5000
#define X 998244353
#define I2 499122177
#define LL long long
#define ull unsigned long long
using namespace std;
namespace FastIO
{
	#define FS 100000
	#define tc() (FA==FB&&(FB=(FA=FI)+fread(FI,1,FS,stdin),FA==FB)?EOF:*FA++)
	#define pc(c) (FC==FE&&(clear(),0),*FC++=c)
	int OT;char oc,FI[FS],FO[FS],OS[30],*FA=FI,*FB=FI,*FC=FO,*FE=FO+FS;
	I void clear() {fwrite(FO,1,FC-FO,stdout),FC=FO;}
	Tp I void read(Ty& x) {x=0;W(!isdigit(oc=tc()));W(x=(x<<3)+(x<<1)+(oc&15),isdigit(oc=tc()));}
	Tp I void writeln(Ty x) {W(OS[++OT]=x%10+48,x/=10);W(OT) pc(OS[OT--]);pc('\n');}
}using namespace FastIO;
int n,m,x,Qt,a[N+5],b[N+5],d[N+5],f1[N+5],f2[N+5],w[N+5],u[N+5];LL K;pair<LL,int> q[N+5];
I int QP(RI x,LL y) {RI t=1;W(y) y&1&&(t=1LL*t*x%X),x=1LL*x*x%X,y>>=1;return t;}
I ull rd(ull& x) {x^=(x<<13),x^=(x>>7),x^=(x<<17);return x;}
I void BF()
{
	RI i,j,p;LL ans=0;for(i=0,j=1;j<=Qt;++i)
	{
		W(q[j].first==i) ans^=1LL*a[x]*q[j++].second;
		for(p=1;p<=n/2;++p) b[p]=1LL*(a[p]+a[n-p+1])*I2%X;for(p=1;p<=n/2;++p) a[2*p-1]=a[2*p]=b[p];
	}writeln(ans);
}
I void Get(CI id)
{
	RI i,s=0;f1[id]=f2[id]=0;for(i=m;i;--i)
	{
		s=(s+(w[i]>0?d[w[i]]:X-d[-w[i]]))%X;
		f1[id]=(f1[id]+2LL*s)%X,2*(i-1)<x&&x<=2*i&&(f2[id]=s);
	}
}
int main()
{
	freopen("noodle.in","r",stdin),freopen("noodle.out","w",stdout);
	RI Id,Tt,i,j,p,o,pw,st,ct,S,Inv;ull sd;LL ans;read(Id),read(Tt),read(sd);W(Tt--)
	{
		for(read(n),read(Qt),read(x),read(K),S=0,i=1;i<=n;++i) read(a[i]),S=(S+a[i])%X;
		for(ans=0,i=1;i<=Qt;++i) q[i]=make_pair(rd(sd)%K,i);sort(q+1,q+Qt+1);
		if(K<=10) {BF();continue;}
		for(i=0,j=1;!(n&1)&&j<=Qt;++i)
		{
			W(q[j].first==i) ans^=1LL*a[x]*q[j++].second;
			for(n>>=1,x=x+1>>1,S=1LL*S*I2%X,p=1;p<=n;++p) a[p]=1LL*(a[p]+a[2*n-p+1])*I2%X;
		}
		W(q[j].first==i) ans^=1LL*a[x]*q[j++].second;st=i+1;
		for(m=n>>1,i=1;i<=m;++i) a[i]=1LL*(a[i]+a[n-i+1])*I2%X;
		for(i=1;i<=m;++i) d[i]=(a[i]-a[i+1]+X)%X,w[i]=i;Get(0);
		ct=0;W(true)
		{
			++ct;RI A=1,B=m,C=0;W(A<=B) u[++C]=-w[B--],A<=B&&(u[++C]=w[A++]);
			for(i=1;i<=m;++i) w[i]=u[i];for(i=1;i<=m&&w[i]==i;++i);if(i>m) break;Get(ct);
		}
		Inv=QP(n,X-2);W(j<=Qt)
		{
			o=(q[j].first-st)%ct,pw=QP(I2,q[j].first-st);
			ans^=(1LL*(S-1LL*f1[o]*pw%X+X)*Inv+1LL*f2[o]*pw)%X*q[j++].second;
		}
		writeln(ans);
	}return clear(),0;
}