// Cc!FN0I$w3ILAIKeQI?
// 10pts I HATE DIRTY WORKS
#include <cstdio>
#include <cstring>
using namespace std;

typedef long long ll;
// #define int ll
const int max_n = 2000000;
const ll ti = 499122177, mod = 998244353;

int a[max_n], n, x;

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

namespace Subtask1
{
	int sim(int cnt)
	{
		static int b[max_n];
		for (int i = 0; i < n; i++) b[i] = a[i];
		for (int i = 0; i < cnt; i++)
		{
			for (int j = (n >> 1); j < n; j++)
				b[n-j-1] += b[j];
			for (int j = n - 2; j >= 0; j--)
				b[j+1] = b[j] = ti * b[j>>1] % mod;
			// for (int j = 0; j < n; j++)
			// 	fprintf(stderr, "%d%c", b[j], " \n"[j == n - 1]);
		}
		return b[x-1];
	}
}

namespace Subtask2
{
	const int max_k = 10;
	int c[max_k];
	
	int dfs(int id, int ly)
	{
		if (ly == 0)
			return a[id];
		id >>= 1;
		return ti * (dfs(id, ly - 1) + dfs(n - id - 1, ly - 1)) % mod;
	}
	
	void init() { memset(c, -1, sizeof c); }
	
	int solve(int ly)
	{
		if (c[ly] == -1)
			c[ly] = dfs(x - 1, ly);
		return c[ly];
	}
}

ll qpow(ll bs, ll ix)
{
	ll mul = bs, cur = 1, ans = 1;
	while (cur <= ix)
	{
		if (cur & ix)
			ans = (ans * mul) % mod;
		mul = mul * mul % mod;
		cur <<= 1;
	}
	return ans;
}

namespace Subtask3
{
	const int max_lgn = 21;
	ll b[max_n], rb[max_lgn+1];
	ll c[max_n+1], fct[max_n+1], rkf[max_n], rkc[max_n], cx, ca, sm, tl;
	ll tf, tc, itf;
	bool vis[max_n+1];
	
	void smallsim()
	{
		sm = 0;
		for (int i = 0; i < n; i++)
		{
			b[i] = a[i];
			sm = (sm + a[i]) % mod;
		}
		
		rb[0] = a[x-1];
		for (int i = 0; i < max_lgn; i++)
		{
			for (int j = (n >> 1); j < n; j++)
				b[n-j-1] += b[j];
			for (int j = n - 2; j >= 0; j--)
				b[j+1] = b[j] = ti * b[j>>1] % mod;
			rb[i+1] = b[x-1];
		}
		cx = rb[max_lgn - 1];
		for (ca = 1; ca < n; ca++)
			if (b[ca-1] != b[ca])
				break;
	}
	
	void bigsim()
	{
		if (ca == n) ca = 0;
		vis[ca] = true;
		c[ca] = rkc[0] = 0, fct[ca] = rkf[0] = 1;
		
		ll tmpd;
		int nca;
		
		tl = 1;
		if (ca == n / 2)
			nca = 0;
		else if (ca > n / 2)
			nca = 2 * (n - ca);
		else
			nca = 2 * ca;
		while (!vis[nca])
		{
			vis[nca] = true;
			
			tmpd = qpow(2 * n - 2 * ca, mod - 2);
			fct[nca] = (n - 2 * ca) * tmpd % mod;
			c[nca] = (sm * tmpd + fct[nca] * c[ca]) % mod;
			fct[nca] = fct[nca] * fct[ca] % mod;
			rkc[tl] = c[nca], rkf[tl] = fct[nca];
			// fprintf(stderr, "%lld %d %lld %lld %lld %lld %lld\n", ca, nca, sm, fct[ca], c[ca], fct[nca], c[nca]);
			ca = nca;
			
			if (ca == n / 2)
				nca = 0;
			else if (ca > n / 2)
				nca = 2 * (n - ca);
			else
				nca = 2 * ca;
			tl++;
		}
		
		tmpd = qpow(2 * n - 2 * ca, mod - 2);
		tf = (n - 2 * ca) * tmpd % mod;
		tc = (sm * tmpd + tf * c[ca]) % mod;
		tf = tf * fct[ca] % mod;
		itf = qpow(tf - 1, mod - 2); // ?
	}
	
	int solve(ll k)
	{
		if (k <= max_lgn)
			return rb[k];
		return b[x-1];
		k -= max_lgn;
		
		ll tr = k / tl, tk = k - tr * tl, an = qpow(tf, tr);
		// fprintf(stderr, "%lld %lld %lld %lld %lld %lld %lld %lld %lld %lld %lld\n", an, tf, tr, tk, tl, b[x-1], an - 1, itf, tc, rkf[tk], rkc[tk]);
		return (((an * b[x-1] + (an - 1) * itf % mod * tc) % mod * rkf[tk] + rkc[tk]) % mod + mod) % mod;
	}
}

signed main()
{
	freopen("noodle.in", "r", stdin);
	freopen("noodle.out", "w", stdout);
	
	int test, T, q;
	ll k, k_max, res;
	unsigned long long seed;
	
	scanf("%d%d%llu", &test, &T, &seed);
	
	while (T--)
	{
		res = 0;
		// Subtask2::init();
		
		scanf("%d%d%d%lld", &n, &q, &x, &k_max);
		for (int i = 0; i < n; i++)
			scanf("%d", a + i);
		Subtask3::smallsim();
		Subtask3::bigsim();
		for (int i = 0; i < q; i++)
		{
			k = rd(seed) % k_max;
			if (test == 1)
				res ^= 1ll * (i + 1) * Subtask1::sim(k);
			// fprintf(stderr, "%d\n", Subtask1::sim(k));
			// res ^= 1ll * (i + 1) * Subtask2::solve(k);
			// fprintf(stderr, "%lld %d\n", k, Subtask3::solve(k));
			else
				res ^= 1ll * Subtask3::solve(k) * (i + 1);
		}
		
		printf("%lld\n", res);
	}
	
	return 0;
}