#include<bits/stdc++.h>
#define int long long
#define ll long long
#define up(i,x,y) for(int i=x,i##E=y;i<=i##E;++i)
#define down(i,x,y) for(int i=x,i##E=y;i>=i##E;--i)
#define upn up(i,1,n)
#define up_(x) up(i,1,x)
#define pii pair<int,int>
#define fi first
#define se second
#define opl(x) printf("%lld",x)
#define opls(x) printf("%lld ",x)
#define opd(x) printf("%d",x)
#define opds(x) printf("%d ",x)
#define mc cerr<<"qwq\n"
#define edl puts("")

using namespace std;
int n,m;
const int mod=998244353;

unsigned long long rd(unsigned long long &x) {
	x ^= (x << 13);
	x ^= (x >> 7);
	x ^= (x << 17);
	return x;
}
unsigned long long seed;
int test;
int qpow(int a,int b=mod-2)
{
	int ans=1;
	while(b)
	{
		if(b&1)ans=ans*a%mod;
		a=a*a%mod;
		b>>=1;
	}
	return ans;
}
int q,x,k_max;
const int maxn=2e6+10;
int a[maxn];int k;
int i2;
int b[maxn],ans[maxn];
void brute_solve()
{
	ans[0]=a[x];
	up(j,1,k_max)
	{
		upn b[i]=(a[i]+a[n-i+1])%mod;
		upn a[i]=b[(i+1)/2]*i2%mod;
		ans[j]=a[x];
	}
	int w=0;
	up_(q)
	{
		k=rd(seed)%k_max;
		w^=(1ll*ans[k]*i);
	}
	opl(w);edl;
}
void BF2_solve()
{
	ans[0]=a[x];
	up(j,1,24)
	{
		upn b[i]=(a[i]+a[n-i+1])%mod;
		upn a[i]=b[(i+1)/2]*i2%mod;
		ans[j]=a[x];
	}
	int w=0;
	up_(q)
	{
		k=rd(seed)%k_max;
		k=min(k,24ll);
		w^=(1ll*ans[k]*i);
	}
	opl(w);edl;
}
int mx;
struct node
{
	int mp[155][155];
	node()
	{
		memset(mp,0,sizeof(mp));
	}
	node operator *(const node &x)const
	{
		node ans;
		up(kk,1,mx)
		{
			up(i,1,mx)
			{
				up(j,1,mx)
				{
					ans.mp[i][j]+=mp[i][kk]*x.mp[kk][j]%mod;
					ans.mp[i][j]%=mod;
				}
			}
		}
		return ans;
	}
};
void BF3_solve()
{
	mx=n;
	node base;
	memset(base.mp,0,sizeof(base.mp));
	for(int i=1;i<=n;i++)
	{
		if(i<=n/2)
		{
			base.mp[i][i*2-1]+=i2;base.mp[i][i*2]+=i2;
		}
		else
		{
			int I=n-i+1;
			base.mp[i][I*2-1]+=i2;base.mp[i][I*2]+=i2;
		}
	}
	int w=0;
	up_(q)
	{
		k=rd(seed)%k_max;
		node anss,pw;
		memset(pw.mp,0,sizeof(pw.mp));
		up(j,1,mx)
		{
			up(k,1,mx)
			{
				pw.mp[j][k]=base.mp[j][k];
		//		cout<<pw.mp[j][k]<<" ";
			}
		}
		memset(anss.mp,0,sizeof(anss.mp));
		up(j,1,mx)anss.mp[j][j]=1;
		int bb=k;
		while(bb)
		{
			if(bb&1)anss=anss*pw;
			pw=pw*pw;
			bb>>=1;
		}
		int tt=0;
		up(j,1,n)
		{
//			cout<<ans.mp[j][x]<<" ";
			tt+=anss.mp[j][x]*a[j]%mod;tt%=mod;
		}
		
//		pw=pw*pw;
//		cout<<x<<" "<<k<<" "<<tt;edl;
//		up(j,1,n)
//		{
//			up(t,1,n)
//			{
//				cout<<pw.mp[j][t]<<" ";
//			}
//			edl;
//		}
		w^=(1ll*tt*i);
	}
	opl(w);edl;
}
int p[111],qq[111];
void BF4_solve()
{
	mx=2;
	node base;
	ans[0]=a[x];
	up(j,1,24)
	{
		upn b[i]=(a[i]+a[n-i+1])%mod;
		upn a[i]=b[(i+1)/2]*i2%mod;
		ans[j]=a[x];
		p[j]=a[1];qq[j]=a[n];
	}
	int w=0;
	base.mp[1][1]=i2;base.mp[1][2]=1;
	base.mp[2][1]=i2;
	up_(q)
	{
		k=rd(seed)%k_max;
		if(k<=24)
		{
			w^=(1ll*ans[k]*i);
			continue;
		}
		int bb=k-24;
		node anss,pw;
		anss.mp[1][1]=anss.mp[2][2]=1;
		anss.mp[1][2]=anss.mp[2][1]=0;
		pw=base;
		while(bb)
		{
			if(bb&1)anss=anss*pw;
			pw=pw*pw;
			bb>>=1;
		}
		int val=0;
		if(x<=n/3*2)
		{
			val=anss.mp[1][1]*p[24]%mod+anss.mp[2][1]*qq[24]%mod;val%=mod;
		}
		else
		{
			val=anss.mp[1][2]*p[24]%mod+anss.mp[2][2]*qq[24]%mod;val%=mod;
		}
//		cout<<k;edl;
		w^=(1ll*val*i);
	}
	opl(w);edl;
}
signed main()
{
	freopen("noodle.in","r",stdin);
	freopen("noodle.out","w",stdout);
//	freopen("noodle_ex2.in","r",stdin);
	int T;
	cin>>test>>T>>seed;
	i2=qpow(2);
	while(T--)
	{
		scanf("%lld%lld%lld%lld",&n,&q,&x,&k_max);
//		cout<<k_max;edl;
//		cout<<n;edl;
		upn scanf("%lld",&a[i]);
		if(test==7)
		{
			BF4_solve();
			continue;
		}
		if(test>=4&&test<=6)
		{
			BF3_solve();
			continue;
		}
		if(test==1||test==2)
		{
			brute_solve();
			continue;
		}
		if(test==3)
		{
			BF2_solve();
			continue;
		}
		up_(q)
		{
			k=rd(seed)%k_max;
			
		}
	}
	
	return 0;
}
/*

7 1 780237054
12 4 11 200
24 23 2 11 55 8 24 50 9 81 28 43

1 1 780237054
12 4 11 200
24 23 2 11 55 8 24 50 9 81 28 43

7 2 13
4 2 1 3
1 4 2 3
6 2 3 3
6 2 5 3 1 4

4 1 12241232
22 8 4 30
12 35 2 1 53 12 65 1 34 7 39 93 22 34 56 13 67 23 67 22 33 67

1 1 12241232
22 8 4 30
12 35 2 1 53 12 65 1 34 7 39 93 22 34 56 13 67 23 67 22 33 67

*/
