#include <bits/stdc++.h>
using namespace std;
#define file(x) freopen(x".in", "r", stdin), freopen(x".out", "w", stdout);
#define rep(i, a, b) for(ll i = (a); i <= (b); ++ i)
#define per(i, a, b) for(ll i = (a); i >= (b); -- i)
#define pb push_back
#define lowbit(k) (k & (-k))
typedef long long ll;
typedef unsigned long long ull;
const int maxn = 2e6 + 100;
const ll mod = 998244353;
ll read()
{
	ll x;
	scanf("%lld", &x);
	return x;
}

ll chmin(ll &a, ll b){return a = min(a, b);}
ll chmax(ll &a, ll b){return a = max(a, b);}

ll test, t;

ull seed;

ll n, q, x, k_max;

ll a[maxn];

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

struct matrix
{
	ull a[505][505];
	void init(ll x = 0)
	{
		rep(i, 1, n) rep(j, 1, n) a[i][j] = 0;
		rep(i, 1, n) a[i][i] = x;
	}
	friend matrix operator * (matrix a, matrix b)
	{
		matrix ret;
		ret.init(0);
		rep(i, 1, n) rep(k, 1, n)
		{
			ll tmp = 16 - n % 16;
			rep(j, 1, n) 
			{
				ret.a[i][k] += a.a[i][j] * b.a[j][k];
				++ tmp;
				if(tmp == 16) tmp = 0, ret.a[i][k] %= mod;
			}
		}
		return ret;
	}
	friend matrix operator & (matrix a, matrix b)
	{
		matrix ret;
		ret.init(0);
		rep(i, 1, 1) rep(k, 1, n)
		{
			ll tmp = 16 - n % 16;
			rep(j, 1, n) 
			{
				ret.a[i][k] += a.a[i][j] * b.a[j][k];
				++ tmp;
				if(tmp == 16) tmp = 0, ret.a[i][k] %= mod;
			}
		}
		return ret;
	}
	void print()
	{
		rep(i, 1, n)
		{
			rep(j, 1, n) printf("%llu ", a[i][j]);
			puts("");
		}
		puts("");
	}
}
b[62];

matrix get(ll k)
{
	matrix ret;
	rep(i, 1, n) ret.a[1][i] = a[i];
	rep(i, 0, 60)
	{
		if(!(k >> i)) return ret;
		if(k >> i & 1) ret = ret & b[i];
	}
}

ll que[505];

signed main()
{
	file("noodle");
	scanf("%lld%lld%llu", &test, &t, &seed);
	for(int Case = 1; Case <= t; Case ++) {
		scanf("%lld%lld%lld%lld", &n, &q, &x, &k_max);
		for(int i = 1; i <= n; i ++) {
			scanf("%lld", &a[i]);
		}
		if(k_max <= 500 || lowbit(n) == n)
		{
			ll ans = 0;
			rep(i, 0, 500) que[i] = 0;
			ll lim = k_max;
			if(lowbit(n) == n) chmin(lim, 60);
			rep(i, 0, lim)
			{
				que[i] = a[x];
				rep(j, 1, n / 2) a[j] = (a[j] + a[n - j + 1]) * (mod + 1) / 2 % mod;
				per(j, n, 1) a[j] = a[(j + 1) / 2];
			}
			for(int i = 1; i <= q; i ++) {
				long long k = rd(seed) % k_max;
				if(lowbit(n) == n) chmin(k, 60);
				ans ^= que[k] * i;
			}
			printf("%lld\n", ans);
			continue;
		}
		b[0].init(0);
		rep(i, 1, n)
		{
			ll ti = i;
			if(i > n / 2) ti = n - i + 1;
			b[0].a[i][ti * 2 - 1] = b[0].a[i][ti * 2] = (mod + 1) / 2;
		}
		// b[0].print();
		rep(i, 1, 60)
		{
			if(!(k_max >> i)) break;
			b[i] = b[i - 1] * b[i - 1];
			// b[i].print();
		}
		ll ans = 0;
		for(int i = 1; i <= q; i ++) {
			long long k = rd(seed) % k_max;
			matrix tmp = get(k);
			ans ^= i * tmp.a[1][x];
		}
		printf("%lld\n", ans);
	}
	return 0;
}