#include<iostream>
#include<cstring>
#include<cstdio>
#define int long long
#define ull unsigned long long
using namespace std;
const int p=998244353;
const int i2=499122177;
ull seed;
int test,T;
ull rd(ull &x){x^=(x<<13),x^=(x>>7),x^=(x<<17);return x;}
namespace Q1
{
	const int N=2e6+10;
	int ans[N];
	int a[N],A[N];
	int n,q,x,k_max;
	void main()
	{
		while(T--)
		{
			int s=0;
			scanf("%lld%lld%lld%lld",&n,&q,&x,&k_max);
			for(int i=1;i<=n;i++) scanf("%lld",&a[i]);ans[0]=a[x];
			for(int k=1;k<=k_max;k++)
			{
				for(int i=1;i<=n/2;i++) A[i]=a[i]+a[n-i+1];
				for(int i=1;i<=n;i++) a[i]=A[(i+1)/2]*i2%p;
				ans[k]=a[x];
			}
			for(int C=1;C<=q;C++){int k=rd(seed)%k_max;s^=(ans[k]*C);}
			printf("%lld\n",s);
		}
	}
}
namespace Q2
{
	const int N=2e6+10;
	const int M=150;
	const int lim=70;
	int ans[N];
	int a[N],A[N];
	int n,q,x,k_max;
	int lowbit(int x){return x&-x;}
	struct mat
	{
		int n,m;
		int a[M][M];
		mat(){n=m=0,memset(a,0,sizeof(a));}
		void clear(){n=m=0,memset(a,0,sizeof(a));}
	}t[M];
	mat operator * (mat x,mat y)
	{
		mat ans;ans.n=x.n,ans.m=y.m;
		for(int i=1;i<=ans.n;i++) for(int j=1;j<=ans.m;j++)
			for(int k=1;k<=x.m;k++) ans.a[i][j]=(ans.a[i][j]+x.a[i][k]*y.a[k][j]%p)%p;
		return ans;
	}
	void main()
	{
		while(T--)
		{
			int s=0;
			scanf("%lld%lld%lld%lld",&n,&q,&x,&k_max);
			for(int i=1;i<=n;i++) scanf("%lld",&a[i]);ans[0]=a[x];
			for(int k=1;k<=lim;k++)
			{
				for(int i=1;i<=n/2;i++) A[i]=a[i]+a[n-i+1];
				for(int i=1;i<=n;i++) a[i]=A[(i+1)/2]*i2%p;
				ans[k]=a[x];
			}
			if(lowbit(n)==n)
			{
				for(int C=1;C<=q;C++)
				{
					int k=rd(seed)%k_max;
					if(k<=lim) s^=(ans[k]*C);
					else s^=(ans[lim]*C);
				}
				printf("%lld\n",s);continue;
			}
			int Q=lowbit(n)*2;t[0].clear(),t[0].n=n/Q+1,t[0].m=n/Q+1;
			for(int i=1,j=t[0].n,k=1;k<=t[0].m;k++)
			{
				t[0].a[i][k]=(t[0].a[i][k]+i2)%p;
				t[0].a[j][k]=(t[0].a[j][k]+i2)%p;
				k%2?j--:i++;
			}
			for(int i=1;i<=70;i++) t[i]=(t[i-1]*t[i-1]);
			for(int C=1;C<=q;C++)
			{
				int k=rd(seed)%k_max;
				if(k<=lim) s^=(ans[k]*C);
				else
				{
					mat f;f.n=1,f.m=n/Q+1;k-=lim;
					for(int i=1;i<=f.m;i++) f.a[1][i]=a[(i-1)*Q+1];
					for(int i=0;i<=60;i++) if(k&(1ll<<i)) f=(f*t[i]);
					s^=(f.a[1][(x+Q-1)/Q]*C);
				}
			}
			printf("%lld\n",s);
		}
	}
}
signed main()
{
	freopen("noodle.in","r",stdin);
	freopen("noodle.out","w",stdout);
	scanf("%lld%lld%llu",&test,&T,&seed);
	if(test<=2) Q1::main();
	else if(test<=9) Q2::main();
	return 0;
}
