#include <bits/stdc++.h>
using namespace std;

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

typedef unsigned long long ull;
typedef long long ll;

template <typename T>
inline void read(T &f) {
	f = 0; int fu = 0; char c = getchar();
	while (c < '0' || c > '9') {
		if (c == '-') fu = 1;
		c = getchar();
	}
	while (c >= '0' && c <= '9') {
		f = f * 10 + (c - '0');
		c = getchar();
	}
	if (fu) f = -f;
}

const int md = 998244353, inv2 = (md + 1) / 2;

inline int add(int x, int y) {
	if (x + y >= md) return x + y - md;
	return x + y;
}

inline int sub(int x, int y) {
	if (x < y) return x - y + md;
	return x - y;
}

inline int mul(int x, int y) { return 1ull * x * y % md; }

inline int fpow(int x, int y) {
	int ans = 1;
	while (y) {
		if (y & 1) ans = mul(ans, x);
		y >>= 1; x = mul(x, x);
	}
	return ans;
}

const int N = 2e6 + 105;

ull seed;
int a[N], tmp[N * 2], s[30];
int T, n, q, x; ll k_max;

inline int div2(int x) {
	if (x & 1) return (x + md) >> 1;
	return x >> 1;
}

const ll P = 1ll * md * md;

struct mat { int a[155][155]; } pw[60];

int res[155], g[155];

mat operator * (const mat a, const mat b) {
	mat ans;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			ll sum = 0;
			for (int k = 1; k <= n; k++) {
				sum += 1ll * a.a[i][k] * b.a[k][j];
				if (sum >= P) sum -= P;
			}
			ans.a[i][j] = sum % md;
		}
	}
	return ans;
}

int main() {
	freopen("noodle.in", "r", stdin);
	freopen("noodle.out", "w", stdout);
	read(T); read(T); read(seed);
	while (T--) {
		read(n); read(q); read(x); read(k_max);
		for (int i = 1; i <= n; i++) read(a[i]);
		if ((n & (n - 1)) == 0) {
			for (int i = 1; i <= n; i++) tmp[i] = a[i];
			s[0] = 1; int l = 1, r = n;
			for (int i = 1; i <= 21; i++) {
				if (l == r) {
					tmp[l + 1] = tmp[l]; ++l; ++r; s[i] = l;
					continue;
				}
				int len = r - l + 1, L = r + 1, R = r;
				for (int j = 0; j < len / 2; j++) tmp[++R] = div2(add(tmp[l + j], tmp[r - j]));
				l = L; r = R; s[i] = l;
			}
			ll ans = 0;
			for (int i = 1; i <= q; i++) {
				ll k = rd(seed) % k_max;
				if (k <= 21) ans ^= 1ll * i * tmp[s[k] + ((x - 1) >> k)];
				else ans ^= 1ll * i * tmp[s[21]];
			}
			printf("%lld\n", ans);
			continue;
		}
		if (k_max <= 20000000 / n) {
			vector <int> ta(n + 1);
			vector < vector <int> > vec(k_max + 1, ta);
			for (int i = 1; i <= n; i++) vec[0][i] = a[i];
			for (int i = 1; i <= k_max; i++) {
				for (int j = 1; j <= n; j++) {
					vec[i][j] = div2(add(vec[i - 1][(j + 1) >> 1], vec[i - 1][n - ((j + 1) >> 1) + 1]));
				}
			}
			ll ans = 0;
			for (int i = 1; i <= q; i++) {
				ll k = rd(seed) % k_max;
				ans ^= 1ll * i * vec[k][x];
			}
			printf("%lld\n", ans);
			continue;
		}
		if (n <= 150) {
			for (int i = 1; i <= n; i++) {
				for (int j = 1; j <= n; j++) {
					pw[0].a[i][j] = 0;
				}
			}
			for (int i = 1; i <= n; i++) {
				pw[0].a[i][(i + 1) / 2] = inv2;
				pw[0].a[i][n - (i + 1) / 2 + 1] = inv2;
			}
			for (int i = 1; i <= 59; i++) pw[i] = pw[i - 1] * pw[i - 1];
			ll ans = 0;
			for (int i = 1; i <= q; i++) {
				ll k = rd(seed) % k_max;
				for (int j = 1; j <= n; j++) res[j] = a[j];
				for (int b = 0; b <= 59; b++) {
					if ((k >> b) & 1) {
						for (int j = 1; j <= n; j++) {
							ll sum = 0;
							for (int k = 1; k <= n; k++) {
								sum += 1ll * pw[b].a[j][k] * res[k];
								if (sum >= P) sum -= P;
							}
							g[j] = sum % md;
						}
						for (int j = 1; j <= n; j++) res[j] = g[j];
					}
				}
				ans ^= 1ll * i * res[x];
			}
			printf("%lld\n", ans);
			continue;
		}
	}
	return 0;
}
