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

#define int long long
#define rep(i, a, b) for(int i = a; i <= b; ++i)
#define per(i, a, b) for(int i = a; i >= b; --i)
#define siz(a) ((int)(a.size()))
#define vi vector<int>
#define PB emplace_back

const int N = 500, mod = 998244353;
struct mat {
	int n, m, s[N + 5][N + 5];
	mat(int _n = 0, int _m = 0) {n = _n, m = _m, memset(s, 0, sizeof(s));}
	int* operator[](int n) {return s[n];}
	mat operator*(const mat &o) const {
		mat res(n, o.m);
		rep(k, 1, m) rep(i, 1, n) rep(j, 1, o.m)
		(res.s[i][j] += s[i][k] * o.s[k][j]) %= mod;
		return res;
	}
	void print() {rep(i, 1, n) rep(j, 1, m) cout << s[i][j] << " \n"[j == m];}
} S;

mat operator^(mat n, int m) {
	mat res = n;
	for(--m; m; m >>= 1) {
		if(m & 1) res = res * n;
		n = n * n;
	}
	return res;
}
unsigned long long rd(unsigned long long &x) {
	x ^= (x << 13);
	x ^= (x >> 7);
	x ^= (x << 17);
	return x;
}

const int M = 2e6;
int a, b, s[M + 5];
unsigned long long seed;

void ini(int n) {
	S = mat(n / 2, n / 2);
	rep(i, 1, n / 2) ++S[i][min(n - (2 * i - 1) + 1, 2 * i - 1)], ++S[i][min(n - 2 * i + 1, 2 * i)];
}
int qpow(int n, int m = mod - 2) {
	int res = 1;
	for(; m; m >>= 1) {
		if(m & 1) res = res * n % mod;
		n = n * n % mod;
	}
	return res;
}
namespace sub1 {
	void ANS(int x, int n) {
		vi t[n];
		rep(i, 0, n - 1) t[i].resize(a + 1);
		rep(i, 1, a) t[0][i] = s[i];
		const int i2 = (mod + 1) / 2;
		rep(i, 1, n - 1) rep(j, 1, a) t[i][j] = (t[i - 1][(j + 1) / 2] + t[i - 1][a - (j + 1) / 2 + 1]) * i2 % mod;
		int res = 0;
		rep(i, 1, b) {
			long long k = rd(seed) % n;
			res ^= t[k][x] * i;
		}
		cout << res << '\n';
	}
}
namespace sub2 {
	void ANS(int x, int n) {
		vi t[20];
		t[0].resize(a + 1);
		rep(i, 1, a) t[0][i] = s[i];
		int tot = 0;
		for(int i = 1, j = 2; j <= a; ++i, j <<= 1) {
			t[i].resize(a / j + 1);
			rep(k, 1, a / j) t[i][k] = t[i - 1][k] + t[i - 1][a / j * 2 - k + 1];
			tot = i;
		}
		int res = 0;
		rep(i, 1, b) {
			long long k = rd(seed) % n;
			if(k >= 20 || (1 << k) >= a) res ^= t[tot][1] * qpow((mod + 1) / 2, a) % mod * i;
			else res ^= t[k][(x + (1 << k) - 1) / (1 << k)] * qpow((mod + 1) / 2, k) % mod * i;
		}
		cout << res << '\n';
	}
}
map<int, bool> mp;

signed main() {
	freopen("noodle.in", "r", stdin);
	freopen("noodle.out", "w", stdout);
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	mp[1] = mp[2] = mp[4] = mp[8] = mp[16] = mp[32] = mp[64] = mp[128] = mp[256] = mp[512]
	= mp[1024] = mp[2048] = mp[4096] = mp[8192] = mp[16384] = mp[32768] = mp[65536]
	= mp[131072] = mp[262144] = mp[524288] = mp[1048576] = 1;
//	a = 12;
//	S = mat(a / 2, a / 2);
//	rep(i, 1, a / 2) ++S[i][min(a - (2 * i - 1) + 1, 2 * i - 1)], ++S[i][min(a - 2 * i + 1, 2 * i)];
//	(S ^ 8).print();
	int test, T;
	cin >> test >> T >> seed;
	int x, k_max;
	for(int Case = 1; Case <= T; Case ++) {
		cin >> a >> b >> x >> k_max;
		rep(i, 1, a) cin >> s[i];
		if(k_max <= 500) {
			sub1::ANS(x, k_max);
			continue;
		}
		if(mp.count(a)) {
			sub2::ANS(x, k_max);
			continue;
		}
		ini(a);
		int res = 0;
		rep(i, 1, b) {
			long long k = rd(seed) % k_max;
			if(!k) {
				res ^= s[x] * i;
				continue;
			}
			if(k == 1) {
				res ^= (s[(x + 1) / 2] + s[a - ((x + 1) / 2) + 1]) * qpow(2) % mod * i;
				continue;
			}
			mat T = S ^ (k - 1);
//			T.print();
			int ans = 0;
			rep(j, 1, a / 2) (ans += T[j][(x + 1) / 2] * (s[j] + s[a - j + 1])) %= mod;
			(ans *= qpow(qpow(2, k))) %= mod;
//			cout << ans << endl;
			res ^= ans * i;
		}
		cout << res << '\n';
	}
	return 0;
}
