#include<algorithm>
#include<cstdio>
const int Q = 2000010,N = 1000010;
const long long Mod = 998244353;
struct Query{
	long long k,num;
}q[Q];
struct Matrix{
	int h;
	long long num[1010][1010];
}Mx[70],M1,M;
long long a[N],p,p1,ans,g;
unsigned long long seed,k_max;
int test,T,n,m,x;
unsigned long long rd(unsigned long long &x)
{
	x ^= (x<<13);
	x ^= (x>>7);
	x ^= (x<<17);
	return x;
}
bool cmp(Query x,Query y)
{
	return x.k < y.k;
}
void _pow(long long kk)
{
	for (long long i = 0;(1ll<<i) <= kk;++i)
		if (kk&(1ll<<i))
		{
			for (int j = 1;j <= n;++j)
				for (int k = 1;k <= n;++k)
				{
					M1.num[j][k] = 0;
					for (int l = 1;l <= n;++l)
						M1.num[j][k] = (M1.num[j][k]+M.num[j][l]*Mx[i].num[l][k])%Mod;
				}
			for (int j = 1;j <= n;++j)
				for (int k = 1;k <= n;++k)
					M.num[j][k] = M1.num[j][k];
		}
}
int main()
{
	freopen("noodle.in","r",stdin);
	freopen("noodle.out","w",stdout);
	scanf("%d%d%llu",&test,&T,&seed);
	while (T--)
	{
		scanf("%d%d%d%llu",&n,&m,&x,&k_max),ans = 0;
		for (int i = 1;i <= n;++i)
			scanf("%lld",&a[i]);
		for (int i = 1;i <= m;++i)
			q[i] = (Query){(long long)(rd(seed)%k_max),i};
		std::sort(q+1,q+m+1,cmp),p = 1,p1 = 0,q[0].k = 0;
		while (p <= m && q[p].k == 0)
			ans ^= a[x]*q[p++].num;
		while (!(n&1))
		{
			for (int i = 1;i <= n/2;++i)
				a[i] = (a[i]+a[n-i+1])*499122177%Mod;
			x = (x+1)/2,n /= 2,++p1;
			while (p <= m && q[p].k == p1)
				ans ^= a[x]*q[p++].num;
		}
		for (int i = 1;i <= n/2;++i)
			a[i] = (a[i]+a[n-i+1])*499122177%Mod;
		n = n/2+1,x = (x+1)/2,++p1,g = 0;
			while (p <= m && q[p].k == p1)
				ans ^= a[x]*q[p++].num;
		for (int i = p;i <= m;++i)
			g = std::max(g,q[i].k-q[i-1].k);
		for (int i = 1;i <= n;++i)
			for (int j = 1;j <= n;++j)
				Mx[0].num[i][j] = 0;
		for (int i = 1;i < n;++i)
			Mx[0].num[i][(i+1)/2] = Mx[0].num[i][(n-i/2)] = 499122177;
		Mx[0].num[Mx[0].h = n][(n+1)/2] = 1;
		for (int i = 1;(1ll<<i) <= g;++i)
		{
			Mx[i].h = Mx[i-1].h;
			for (int j = 1;j <= Mx[i].h;++j)
				for (int k = 1;k <= Mx[i].h;++k)
				{
					Mx[i].num[j][k] = 0;
					for (int l = 1;l <= Mx[i].h;++l)
						Mx[i].num[j][k] = (Mx[i].num[j][k]+Mx[i-1].num[j][l]*Mx[i-1].num[l][k])%Mod;
				}
		}
		q[p-1].k = p1,M.h = n;
		for (int i = 1;i <= n;++i)
			for (int j = 1;j <= n;++j)
				M.num[i][j] = i == j;
		for (int i = p;i <= m;++i)
		{
			if (n > 1)
				_pow(q[i].k-q[i-1].k);
			p = 0;
			for (int j = 1;j <= n;++j)
				p = (p+M.num[x][j]*a[j])%Mod;
			ans ^= p*q[i].num;
		}
		printf("%lld\n",ans);
	}
	return 0;
}
