#include <bits/stdc++.h>

#define see(x) std::cout << #x << " = " << x << std::endl

template <class T, typename = typename T::iterator>
std::ostream &operator<< (std::ostream &out, const T &v)
{
	out << "{";
	for (const auto &x : v) out << x << ", ";
	out << "}";
	return out;
}

int init_io = []{
#ifndef CM_DEBUG
	freopen("noodle.in", "r", stdin);
	freopen("noodle.out", "w", stdout);
#endif
	return 0;
}();

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

int test, t;
unsigned long long seed;
int n, q, x;
long long k_max;

const int MOD = 998244353;
const uint64_t BMOD = (uint64_t)(MOD) * MOD * 16;
const int inv2 = (MOD + 1) / 2;
const int N = 2000005;
std::vector<int> a;

std::vector<int> make(const std::vector<int> &a)
{
	std::vector<int> r(n);
	for (int i = 0; i < n; i++)
		r[i] = (int64_t)(inv2) * (a[i / 2] + a[n - 1 - i / 2]) % MOD;
	return r;
}

void brute()
{
	std::vector<std::vector<int>> as(k_max);
	as[0] = a;
	for (int i = 0; i + 1 < k_max; i++)
		as[i + 1] = make(as[i]);

	int64_t ans = 0;
	for (int i = 0; i < q; i++)
	{
		long long k = rd(seed) % k_max;
		ans ^= (int64_t)(i + 1) * as[k][x];
	}
	printf("%" SCNi64 "\n", ans);
}

struct matrix_t
{
	std::vector<std::vector<int>> a;
	int n;

	matrix_t() = default;
	matrix_t(int n) : a(n, std::vector<int>(n)), n(n) {}

	matrix_t operator* (const matrix_t &rhs) const
	{
		static uint64_t r[505][505];
		for (int i = 0; i < n; i++) 
			for (int j = 0; j < n; j++)
				r[i][j] = 0;

		for (int i = 0; i < n; i++)
			for (int k = 0; k < n; k++)
				for (int j = 0; j < n; j++)
				{
					r[i][j] += (uint64_t)(a[i][k]) * rhs.a[k][j];
					if (r[i][j] >= BMOD)
						r[i][j] -= BMOD;
				}

		matrix_t c(n);
		for (int i = 0; i < n; i++)
			for (int j = 0; j < n; j++)
				c.a[i][j] = r[i][j] % MOD;
		
		return c;
	}

	std::vector<int> operator* (const std::vector<int> &rhs) const
	{
		std::vector<int> res(n);
		for (int i = 0; i < n; i++)
		{
			uint64_t cur = 0;
			for (int j = 0; j < n; j++)
			{
				cur += (uint64_t)(a[i][j]) * rhs[j];
				if (cur >= BMOD) cur -= BMOD;
			}
			res[i] = cur % MOD;
		}
		return res;
	}
};

matrix_t get_trans(int n)
{
	matrix_t t(n);
	for (int i = 0; i < n; i++)
	{
		(t.a[i][i / 2] += inv2) %= MOD;
		(t.a[i][n - 1 - i / 2] += inv2) %= MOD;
	}
	return t;
}

void sol()
{
	int nk = 1;
	while (n % (1 << (nk + 1)) == 0)
		nk += 1;

	std::vector<std::vector<int>> prev(nk);
	prev[0] = a;
	for (int i = 0; i + 1 < nk; i++)
		prev[i + 1] = make(prev[i]);

	auto _base = make(prev.back());
	std::vector<int> bs(n >> nk);
	for (int i = 0; i < (n >> nk); i++)
		bs[i] = _base[i << nk];

	const int B = 62;
	std::vector<matrix_t> powt(B);
	powt[0] = get_trans(n >> nk);
	for (int i = 0; i + 1 < B; i++)
		powt[i + 1] = powt[i] * powt[i];

	int64_t ans = 0;
	for (int i = 0; i < q; i++)
	{
		long long k = rd(seed) % k_max;
		int cur_ans = 0;
		if (k < nk)
		{
			cur_ans = prev[k][x];
		}
		else
		{
			k -= nk;
			auto c = bs;
			for (int i = 0; i < B; i++)
				if (k & (1ll << i))
					c = powt[i] * c;
			cur_ans = c[x >> nk];
		}
		ans ^= (int64_t)(i + 1) * cur_ans;
	}
	printf("%" SCNi64 "\n", ans);
}

int main()
{
	scanf("%d%d%llu", &test, &t, &seed);
	for (int i = 0; i < t; i++)
	{
		scanf("%d%d%d%lld", &n, &q, &x, &k_max);
		x -= 1;
		a.resize(n);
		for (int i = 0; i < n; i++)
			scanf("%d", &a[i]);

		if (test <= 2)
			brute();
		else
			sol();
	}
	return 0;
}
