#include <bits/stdc++.h>
#define p 998244353
#define n2 499122177
#define ll long long
using namespace std;
int P(int x,ll y=p-2)
{
	int z=1;
	for(;y;x=1ll*x*x%p,y>>=1)if(y&1)z=1ll*z*x%p;
	return z;
}
unsigned long long rd(unsigned long long &x){x^=(x<<13),x^=(x>>7),x^=(x<<17);return x;}
int n,q,x;ll k_max,tans;
int a[24][2000005],b[1000005],c[1000005],cn;
int to[1000005],bw[1000005],vi[1000005];
void add(int u,int v,int w){to[u]=v,bw[u]=w;}
int hs[1000005],qw[1000005],qn[1000005],hw[1000005],hr[1000005],xh[1000005],hn;
int cc[1000005];
int main()
{
	freopen("noodle.in","r",stdin);
	freopen("noodle.out","w",stdout);
	int test,T;
	unsigned long long seed;
	scanf("%d%d%llu", &test, &T, &seed);
	for(int Case=1;Case<=T;Case++)
	{
		scanf("%d%d%d%lld",&n,&q,&x,&k_max),tans=0;
		for(int i=1;i<=n;i++)scanf("%d",&a[0][i]);
		if(test<=2)
		{
			for(int t=1;t<=k_max;t++)
			{
				for(int i=1;i<=n/2;i++)b[i]=a[t-1][i]+a[t-1][n-i+1],b[i]-=b[i]>=p?p:0;
				for(int i=1;i<=n/2;i++)b[i]=1ll*b[i]*n2%p,a[t][2*i-1]=a[t][2*i]=b[i];
			}
			for(int i=1;i<=q;i++)
			{
				ll k=rd(seed)%k_max;int ans=a[k][x];
				tans^=1ll*ans*i;
			}
		}
		else if(test==3)
		{
			int t=1,mi=1;
			for(;mi<n;++t)
			{
				for(int i=1;i<=n/2;i++)b[i]=a[t-1][i]+a[t-1][n-i+1],b[i]-=b[i]>=p?p:0;
				for(int i=1;i<=n/2;i++)b[i]=1ll*b[i]*n2%p,a[t][2*i-1]=a[t][2*i]=b[i];
				mi<<=1;
			}
			for(int i=1;i<=q;i++)
			{
				ll k=rd(seed)%k_max;int ans=0;
				if(k<=t)ans=a[k][x];
				else ans=a[t][x];
				tans^=1ll*ans*i;
			}
		}
		else if(test<=13)
		{
			int t=1,mi=1;
			for(;mi<n;++t)
			{
				for(int i=1;i<=n/2;i++)b[i]=a[t-1][i]+a[t-1][n-i+1],b[i]-=b[i]>=p?p:0;
				for(int i=1;i<=n/2;i++)b[i]=1ll*b[i]*n2%p,a[t][2*i-1]=a[t][2*i]=b[i];
				mi<<=1;
				if(n%mi!=0)break;
			}
			if(mi!=n)
			{
				cn=0;
				for(int i=1;i+mi<=n;i+=mi)c[++cn]=(a[t][i+mi]-a[t][i]+p)%p;
				int l=1,r=cn;
				for(int i=1;i<=cn;i++)
				{
					vi[i]=0;
					if(i&1)add(r,i,-1),--r;else add(l,i,1),++l;
				}
				hn=0,qw[0]=1;
				for(int i=1;i<=cn;i++)if(!vi[i])
				{
					int u=i,l=hn;
					while(!vi[u])vi[u]=1,++hn,xh[hn]=u,qw[hn]=bw[u],u=to[u];
					int ww=1;
					for(int j=l+1;j<=hn;j++)ww=1ll*ww*qw[j]%p,qw[j]=1ll*qw[j]*qw[j-1]%p;
					for(int j=l+1;j<=hn;j++)hs[j]=hn-l,hw[j]=ww,hr[j]=hn;
				}
			}
			int ta=0;
			for(int i=1;i<=n;i++)ta+=a[0][i],ta-=ta>=p?p:0;
			for(int i=1;i<=q;i++)
			{
				ll k=rd(seed)%k_max;int ans=0;
				if(k<=t)ans=a[k][x];
				else if(mi==n)ans=a[t][x];
				else
				{
					k-=t;
					ll hh;int r,hhw=P(n2,k);
					for(int j=1;j<=cn;j++)
					{
						if(j==1||hr[j-1]==j-1)hh=k/hs[j],r=k%hs[j];
						if(j+r>hr[j])
						{
							int nw=j+r-hs[j];
							cc[nw]=1ll*qw[hr[j]]*qn[j-1]%p*qw[nw-1]%p*qn[hr[j]-hs[j]]%p*hhw%p;
							cc[nw]+=cc[nw]<0?p:0;
						}
						else
						{
							int nw=j+r;
							cc[nw]=1ll*qw[nw-1]*qn[j-1]*hhw%p;
							cc[nw]+=cc[nw]<0?p:0;
						}
					}
					int tc=0;
					for(int j=mi;j<=n;j+=mi)tc=(tc+1ll*cc[j/mi]*(n-mi))%p;
					int ka=1ll*(ta-tc+p)*P(n)%p;
					for(int j=1;j<=n;j+=mi)
					{
						int rj=j+mi-1;
						if(x<=rj){ans=ka;break;}
						ka=(ka+cc[rj/mi])%p;
					}
				}
				tans^=1ll*ans*i;
			}
		}
		printf("%lld\n",tans);
	}
}
