#include<bits/stdc++.h>

using namespace std;

const int N=2e6+5, LG=22, MOD=998244353;

unsigned long long rd(unsigned long long &x) { x^=(x<<13); x^=(x>>7); x^=(x<<17); return x; }

int power(int x, int y)
{
	int res=1;
	for(int now=x; y>0; y>>=1, now=1ll*now*now%MOD) if(y&1) res=1ll*res*now%MOD;
	return res;
}
int inv(int x) { return power(x, MOD-2); }

int n, q, pos; long long k_max;
unsigned long long seed;

namespace Brute
{
	const int M=155;
	struct Matrix
	{
		int z[M][M];
		Matrix ()
		{
			memset(z, 0, sizeof z);
			return;
		}
		Matrix operator * (Matrix Oth)
		{
			Matrix Res;
			for(int k=0; k<M; k++)
			{
				for(int i=0; i<M; i++)
				{
					if(z[i][k]==0) continue;
					for(int j=0; j<M; j++)
					{					
						if(Oth.z[k][j]==0) continue;
						(Res.z[i][j]+=1ll*z[i][k]*Oth.z[k][j]%MOD)%=MOD;
					}
				}
			}
			return Res;
		}
	} Base;
	Matrix power(Matrix X, long long y)
	{
		Matrix Res;
		for(int i=0; i<M; i++) Res.z[i][i]=1;
		for(Matrix Now=X; y>0; y>>=1, Now=Now*Now) if(y&1) Res=Res*Now;
		return Res;	
	}
	
	int a[M];
	void main()
	{
		for(int i=1; i<=n; i++) scanf("%d", &a[i]);
		int iv2=inv(2);
		memset(Base.z, 0, sizeof Base.z);
		for(int i=1; i<=n/2; i++) Base.z[i*2-1][i]=Base.z[i*2-1][n+1-i]=Base.z[i*2][i]=Base.z[i*2][n+1-i]=iv2;
		long long ans=0;
		for(int i=1; i<=q; i++)
		{
			long long k=rd(seed)%k_max;
			Matrix Tmp=power(Base, k);
			int res=0;
			for(int j=1; j<=n; j++) (res+=1ll*Tmp.z[pos][j]*a[j]%MOD)%=MOD;
			ans^=(1ll*i*res);
		}
		printf("%lld\n", ans);
	}
}

struct Matrix
{
	int z[2][2];
	Matrix ()
	{
		memset(z, 0, sizeof z);
		return;
	}
	Matrix operator * (Matrix Oth)
	{
		Matrix Res;
		for(int i=0; i<2; i++)
		{
			for(int j=0; j<2; j++)
			{
				for(int k=0; k<2; k++)
				{
					(Res.z[i][j]+=1ll*z[i][k]*Oth.z[k][j]%MOD)%=MOD;
				}
			}
		}
		return Res;
	}
} Base;
Matrix power(Matrix X, long long y)
{
	Matrix Res;
	for(int i=0; i<2; i++) Res.z[i][i]=1;
	for(Matrix Now=X; y>0; y>>=1, Now=Now*Now) if(y&1) Res=Res*Now;
	return Res;	
}

int f[LG][N];

int main()
{
	freopen("noodle.in", "r", stdin);
	freopen("noodle.out", "w", stdout);
	
	int test, T;
	scanf("%d%d%llu", &test, &T, &seed);
	for(int Case=1; Case<=T; Case++) 
	{
		scanf("%d%d%d%lld", &n, &q, &pos, &k_max);
		
		if(n<=150) 
		{
			Brute::main();
			continue;
		}
		
		for(int i=1; i<=n; i++) scanf("%d", &f[0][i]);
		
		int a=1, b=1, iv2=inv(2);
		for( ; a<=n; b++, a*=2) 
		{
			for(int i=1; i<=n/2; i++) f[b][i]=1ll*(f[b-1][i]+f[b-1][n+1-i])*iv2%MOD;
			for(int i=n; i>=1; i--) f[b][i]=f[b][(i+1)/2];
		}
		a/=2; b--;
				
		Base.z[0][0]=1ll*(2*a-n)*inv(a)%MOD;
		Base.z[0][1]=iv2;
		Base.z[1][0]=1ll*(n-a)*inv(a)%MOD;
		Base.z[1][1]=iv2;
		
		long long ans=0;	
		for(int i=1; i<=q; i++)
		{
			long long k=rd(seed)%k_max;
			if(k<=b)
			{
				ans^=(1ll*i*f[k][pos]);
				continue;
			}
			k-=b;
			Matrix Tmp=power(Base, k);
			int a0=1ll*f[b][1]*a%MOD, b0=1ll*f[b][a+1]*(n-a)%MOD;
			if(pos<=a) 
			{
				int tmp=(1ll*Tmp.z[0][0]*a0%MOD+1ll*Tmp.z[0][1]*b0%MOD)%MOD;
				ans^=(1ll*tmp*inv(a)%MOD*i);
			}
			else
			{
				int tmp=(1ll*Tmp.z[1][0]*a0%MOD+1ll*Tmp.z[1][1]*b0%MOD)%MOD;				
				ans^=(1ll*tmp*inv(n-a)%MOD*i);				
			}
		}
		printf("%lld\n", ans);
	}	
	
	return 0;
}
