#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
const int N = 2e6 + 5, mod = 998244353;
int a[N];
int fpow(int x, int y) {
	int res = 1;
	while (y) {
		if (y & 1) res = 1ll * res * x % mod;
		x = 1ll * x * x % mod, y >>= 1;
	}
	return res;
}
template <typename T> void read(T &x) {
	x = 0; bool f = 0; char c = getchar();
	while (!isdigit(c)) {if (c == '-') f = 1; c = getchar();}
	while (isdigit(c)) x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();
	if (f) x = -x;
}
ull rd(ull &x) {
	x ^= (x << 13);
	x ^= (x >> 7);
	x ^= (x << 17);
	return x;
}
int n, q, x; ll k_max;
int test, T, inv2;
ull seed;
namespace sub1 {
	void func() {
		vector <int> dp[505];
		int km = test <= 2 ? k_max : 17;
		for (int i = 0; i <= km; i++) dp[i].resize(n + 1);
		for (int i = 1; i <= n; i++) read(dp[0][i]);
		for (int i = 1; i <= km; i++) {
			for (int j = 1; j <= n; j++)
				dp[i][j] = 1ll * inv2 * (dp[i - 1][(j + 1) / 2] + dp[i - 1][n - (j + 1) / 2 + 1]) % mod;
//			for (int j = 1; j <= n; j++) printf("%d ", dp[i][j]); printf("\n");
			bool ok = 0;
			for (int j = 2; j <= n; j++)
				if (dp[i][j] != dp[i][1]) {ok = 1; break;}
			if (!ok) {km = i; break;}
		}
		ll ans = 0;
		for (int i = 1; i <= q; i++) {
			ll k = rd(seed) % k_max;
			ans ^= 1ll * dp[min(k, (ll)km)][x] * i;
		}
		printf("%lld\n", ans);
	}
}
namespace sub2 {
	struct matrix {
		int mat[155][155];
		void init() {for (int i = 1; i <= n; i++) mat[i][i] = 1;}
		matrix() {memset(mat, 0, sizeof(mat));}
		int *operator [](int x) {return mat[x];}
	};
	matrix operator * (matrix a, matrix b) {
		matrix res;
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= n; j++) if (a[i][j]) {
				for (int k = 1; k <= n; k++)
					res[i][k] = (res[i][k] + 1ll * a[i][j] * b[j][k]) % mod;
			}
		return res;
	}
	void operator *= (matrix &a, matrix b) {a = a * b;}
	matrix fpow(matrix x, int y) {
		matrix res; res.init();
		while (y) {
			if (y & 1) res *= x;
			x *= x, y >>= 1;
		}
		return res;
	}
	void func() {
		for (int i = 1; i <= n; i++) read(a[i]);
		matrix base; ll ans = 0;
		for (int i = 1; i <= n; i++)
			base[(i + 1) / 2][i] = base[n - (i + 1) / 2 + 1][i] = inv2;
		for (int i = 1; i <= q; i++) {
			ll k = rd(seed) % k_max;
			matrix now = fpow(base, k);
			int res = 0;
			for (int j = 1; j <= n; j++)
				res = (res + 1ll * now[j][x] * a[j]) % mod;
			ans ^= 1ll * res * i;
		}
		printf("%lld\n", ans);
	}
}
//namespace sub3 {
//	int X[505], Y[505]; 
//	void func() {
//		vector <int> dp[505];
//		int ci = 3 * n + 1;
//		for (int i = 0; i <= ci; i++) dp[i].resize(n + 1);
//		for (int i = 1; i <= n; i++) read(dp[0][i]);
//		for (int i = 1; i <= ci; i++)
//			for (int j = 1; j <= n; j++)
//				dp[i][j] = (dp[i - 1][(j + 1) / 2] + dp[i - 1][n - (j + 1) / 2 + 1]) % mod;
//		for (int i = 0; i <= ci; i++) {
//			X[i] = i, Y[i] = dp[i][x];
////			printf("X[%d] = %d, Y[%d] = %d\n", i, X[i], i, Y[i]);
//		}
//		ll ans = 0;
//		for (int i = 1; i <= q; i++) {
//			ll k = rd(seed) % k_max;
////			printf("k = %lld\n", k);
//			int res = 0;
//			for (int j = 0; j <= ci; j++) {
//				int tmp1 = Y[j], tmp2 = 1;
//				for (int l = 0; l <= ci; l++)
//					if (l != j) tmp1 = 1ll * tmp1 * (k - X[l] + mod) % mod, tmp2 = 1ll * tmp2 * (X[j] - X[l] + mod) % mod;
//				res = (res + 1ll * tmp1 * fpow(tmp2, mod - 2)) % mod;
//			}
//			res = 1ll * res * fpow(inv2, k) % mod;
//			ans ^= 1ll * res * i;
//		}
//		printf("%lld\n", ans);
//	}
//}

int main() {
	freopen("noodle.in", "r", stdin);
	freopen("noodle.out", "w", stdout);
	inv2 = fpow(2, mod - 2);
	read(test), read(T), read(seed);
	for (int Case = 1; Case <= T; Case++) {
		read(n), read(q), read(x), read(k_max);
		if (test <= 3) sub1::func();
		else sub2::func();
//		sub3::func();
	}
	return 0;
}
