#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define Mod(x) ((x>=MOD)&&(x-=MOD))
using namespace std;
const int MAXN = 2e6+5;
const int MOD = 998244353;
const ll INV2 = (MOD+1)/2;
int n,test,T,q,x;
ll K_max;
ull seed;
ll A[MAXN],B[MAXN];
struct Ques
{
	ll k;int id;
	bool operator < (const Ques &x)const
	{
		return k<x.k;
	}
}Q[MAXN];
ll qpw(ll x,ll b)
{
	ll r=1;
	for(;b;b>>=1,x=x*x%MOD) if(b&1) r=r*x%MOD;
	return r;
}
unsigned long long rd(unsigned long long &x) {
	x ^= (x << 13);
	x ^= (x >> 7);
	x ^= (x << 17);
	return x;
}
void perform()
{
	for(int i=1;i<=n/2;++i) B[i]=A[i]+A[n-i+1],Mod(B[i]);
	for(int i=1;i<=n;++i) A[i]=B[(i+1)/2]*INV2%MOD;
}
namespace pt10
{
	void Solve()
	{
		ll Ans=0;
		for(int i=1;i<=q;++i)
		{
			for(int j=1;j<=Q[i].k-Q[i-1].k;++j) perform();
			Ans^=(1ll*A[x]*Q[i].id);
		}
		printf("%lld\n",Ans);
	}
}
namespace pt15
{
	void Solve()
	{
		ll up=(ll)log2(n)+1,Ans=0;
		for(int i=1;i<=q;++i)
		{
			if(Q[i].k<up) for(int j=1;j<=Q[i].k-Q[i-1].k;++j)perform();
			else if(Q[i].k>=up&&Q[i-1].k<up) for(int j=1;j<=up;++j) perform();
			Ans^=(1ll*A[x]*Q[i].id);
		}
		printf("%lld\n",Ans);
	}
}
namespace pt30
{
	const int N = 505;
	int M,cnt[505];
	ll C[MAXN];
	struct mat
	{
		ll v[N][N];
		mat(){memset(v,0,sizeof v);}
		void clear()
		{
			memset(v,0,sizeof v);
		}
		mat operator * (const mat &x)const
		{
			mat res;
			for(int k=1;k<=M;++k)for(int i=1;i<=M;++i)for(int j=1;j<=M;++j)
				res.v[i][j]+=v[i][k]*x.v[k][j]%MOD,Mod(res.v[i][j]);
			return res;
		}
	}t,res,t0;
	void Solve()
	{
		t0.clear();res.clear();memset(cnt,0,sizeof cnt);
		ll Ans=0;ll p=0,m=n;int pos=x;
		while(m%2==0) m>>=1,++p;
		if(m==1)
		{
			pt15::Solve();
			return ;
		}
		m=m/2+1;++p;M=m;
		x=(x/(1<<p))+(x%(1<<p)!=0);
		for(int i=1;i<=n;++i) C[i]=A[i];
		ll up=(ll)log2(n)+1;
		for(int i=1;i<=up;++i) perform();
		for(int i=1;i<m;++i)
			res.v[1][i]=A[1ll*i*(1<<p)];
		res.v[1][m]=A[(m-1)*(1<<p)+1];
		for(int i=1;i<=n;++i) A[i]=C[i];
		ll cur=up;
		for(int i=1;i<m;++i) cnt[i]=2;cnt[m]=1;
		int l=1,r=m;
		for(int i=1;i<m;++i)
		{
			t0.v[l][i]=INV2;t0.v[r][i]=INV2;
			cnt[l]--;cnt[r]--;
			if(!cnt[l]) ++l;if(!cnt[r]) --r;
		}
		t0.v[(m+1)/2][m]=1;
		for(int i=1;i<=q;++i)
		{
			ll d=Q[i].k-cur;
			if(Q[i].k<=up)
			{
				for(int j=1;j<=Q[i].k-Q[i-1].k;++j) perform();
				Ans^=(A[pos]*Q[i].id);
			}
			else
			{
				t=t0;
				for(ll j=d;j;j>>=1,t=t*t)
					if(j&1) res=res*t;
				Ans^=(res.v[1][x]*Q[i].id);
			}
			
			if(Q[i].k>=up)cur=Q[i].k;
		}
		printf("%lld\n",Ans);
	}
}
namespace pt35
{
	void Solve()
	{
		
	}
}
int main()
{
	freopen("noodle.in","r",stdin);
	freopen("noodle.out","w",stdout);

//	freopen("noodle_ex2.in","r",stdin);
//	freopen("1.out","w",stdout);

	scanf("%d %d %llu",&test,&T,&seed);
	while(T--)
	{
		scanf("%d %d %d %lld",&n,&q,&x,&K_max);
		for(int i=1;i<=n;++i) scanf("%lld",&A[i]);
		for(int i=1;i<=q;++i) Q[i].k=rd(seed)%K_max,Q[i].id=i;
		sort(Q+1,Q+1+q);
		if(test==1||test==2) pt10::Solve();
		if(test==3) pt15::Solve();
		if(test==4||test==5||test==6||test==8||test==9||test==4) pt30::Solve();

//		cout<<"up:"<<(ll)log2(n)+1<<endl;
//		for(int i=1;i<=q;++i) cout<<Q[i].k<<" ";
//		cout<<endl;
		
//		pt30::Solve();


//		pt10::Solve();
//		pt15::Solve();
	}
	return 0;
}
