#include <bits/stdc++.h>
using namespace std;
#define MOD 998244353
typedef long long ll;
typedef unsigned long long ull;
ull rd(ull &x) {
	x ^= (x << 13);
	x ^= (x >> 7);
	x ^= (x << 17);
	return x;
}
int PLUS(int x, int y) {
	x += y;
	return x >= MOD ? x - MOD : x;
}
int qpow(int x, ll y, const int P) {
	int t = 1;
	for (; y; y>>=1) {
		if (y & 1) t = 1ll * t * x % P;
		x = 1ll * x * x % P;
	} return t;
}
int calc(int p, int _p, int x, int c) {
	if (p < _p) return c + (p <= x && x < _p);
	else if (p == _p) return c;
	else return c + (p <= x || x < _p);
}
int a[2000006], b[2000006];
int main() {
	freopen ("noodle.in", "r", stdin);
	freopen ("noodle.out", "w", stdout);
	int test, T; ull seed;
	scanf ("%d%d%llu", &test, &T, &seed);
	for(int Case = 1; Case <= T; Case ++) {
		int n, q, x; ll k_max, k, ans = 0;
		scanf("%d%d%d%lld", &n, &q, &x, &k_max);
		for (int i=0; i<n; i++)
			scanf ("%d", &a[i]);
		if (test == 2) {
			int seq[30];
			seq[0] = a[x-1];
			for (int i=1; i<=k_max; i++) {
				for (int j=0; j<n>>1; j++)
					b[j] = PLUS(a[j], a[n-1-j]);
				for (int j=0; j<n; j++)
					a[j] = 1ll * (MOD + 1 >> 1) * b[j>>1] % MOD;
				seq[i] = a[x-1];
			}
			for (int t=1; t<=q; t++) {
				k = rd(seed) % k_max;
				ans ^= 1ll * t * seq[k];
			} printf ("%lld\n", ans);
			continue;
		}
		if (test == 3) {
			int seq[30];
			seq[0] = a[x-1];
			for (int i=1; i<=20; i++) {
				for (int j=0; j<n>>1; j++)
					b[j] = PLUS(a[j], a[n-1-j]);
				for (int j=0; j<n; j++)
					a[j] = 1ll * (MOD + 1 >> 1) * b[j>>1] % MOD;
				seq[i] = a[x-1];
			}
			for (int t=1; t<=q; t++) {
				k = rd(seed) % k_max;
				ans ^= 1ll * t * seq[min(k,20ll)];
			} printf ("%lld\n", ans);
			continue;
		}
		int inv = qpow(n << 1, MOD - 2, MOD);
		for (int t=1; t<=q; t++) {
			k = rd(seed) % k_max;
			if (! k) { ans ^= 1ll * t * a[x-1]; continue; }
			int p = 0, d = qpow(2, k, n << 1), q = qpow(2, k, MOD), c = 1ll * (q + MOD - d) * inv % MOD, res = 0;
			q = qpow(q, MOD - 2, MOD);
			for (int i=0; i<n>>1; i++) {
				int _p = p + d; if (_p >= n << 1) _p -= n << 1;
				res = (res + 1ll * (calc(p, _p, x - 1, c) + calc(p, _p, (n << 1) - x, c)) * (a[i] + a[n-1-i]) % MOD * q) % MOD;
				p = _p;
			} ans ^= 1ll * t * res;
		} printf ("%lld\n", ans);
	} return 0;
}