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

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

const int N = 2e6 + 10;
const long long MOD = 998244353;
long long a[N];
long long del[10010][10010], delval[N], K[N], B[N];
long long ksm(long long x, long long y)
{
	long long m = 1;
	for (; y; y >>= 1)
	{
		if(y & 1) m = m * x % MOD;
		x = x * x % MOD;
	}
	return m;
}
long long m[30][N], flag;
long long sum;
long long solve(int n, int N, int len, int olen, int x, long long k)
{
	long long dv = ksm((MOD + 1) >> 1, k);
	if(k <= len)
	{
		int now_num = (x - 1) / (1 << k);
		return (m[k - 1][now_num + 1] + m[k - 1][n / (1 << (k - 1)) - now_num]) * dv % MOD;
	}
	if(N == 1)return sum % MOD * ksm(ksm(2, len), MOD - 2) % MOD;
	k -= len + 1;
	int ori = flag * 2;
	int zong = k / olen, o = k % olen;
	long long _K = 1, _B = 0;
	_K = ksm(K[olen], zong);
	 if(zong) _B = B[olen] * (ksm(K[olen], zong) - 1) % MOD * ksm(K[olen] - 1, MOD - 2) % MOD;
	_K = _K * K[o] % MOD, _B = (K[o] * _B + B[o]) % MOD;
	
	return (sum * (ori * _K + _B) % MOD + delval[o + 1]) * dv % MOD;
}
namespace sub
{
	using namespace std;

	unsigned long long rd(unsigned long long &x) {
		x ^= (x << 13);
		x ^= (x >> 7);
		x ^= (x << 17);
		return x;
	}
	
	const int N = 2e6 + 10;
	const long long MOD = 998244353;
	long long now[11][N], be[N];
	int main(long long T, unsigned long long seed) {
		for(int Case = 1; Case <= T; Case ++) {
			int n, q, x;
			long long k_max;
			cin >> n >> q >> x >> k_max;
			for(int i = 1; i <= n; i ++) cin >> now[0][i];
			long long ans = 0;
			for (int k = 1; k <= 10; ++ k)
				{
					for (int i = 1; i <= n / 2; ++ i) now[k][i] = (now[k - 1][i] + now[k - 1][n - i + 1]) % MOD;
					for (int i = n; i; -- i) now[k][i] = now[k][(i + 1) >> 1] * ((MOD + 1) >> 1) % MOD;
				}
			for(int i = 1; i <= q; i ++)
			{
				long long k = rd(seed) % k_max;
				ans ^= now[k][x] * i;
			}
			cout << ans << "\n";
		}
		return 0;
	}
}
int checko[N];
int main()
{
	freopen("noodle.in", "r", stdin);
	freopen("noodle.out", "w", stdout);
	ios::sync_with_stdio(0); cin.tie(0);
	int test, T;
	unsigned long long seed;
	cin >> test >> T >> seed;
	
	if(test == 2)return sub::main(T, seed);
	
	int n, q, x;
	long long k_max;
	for(int Case = 1; Case <= T; Case ++)
	{
		flag = sum = 0;
		for (int i = 1; i <= n; ++ i)
		for (int j = 1; j <= n; ++ j) del[i][j] = 0;
		
		for (int i = 1; i <= n; ++ i)
		{
			K[i] = B[i] = delval[i] = 0;
			for (int j = 0; j < 30; ++ j) m[j][i] = 0;
		}
		
		cin >> n >> q >> x >> k_max;
		for(int i = 1; i <= n; i ++) cin >> a[i], m[0][i] = a[i], (sum += a[i]) %= MOD;
		int N = n, tot = 0;
		while((N & 1) == 0)
		{
			N >>= 1, ++ tot;
			for (int i = 1; i <= N; ++ i) m[tot][i] = (m[tot - 1][i] + m[tot - 1][i + N]) % MOD;
		}
		long long ans = 0;
		int now_num = (x - 1) / (1 << (tot + 1));
		++ del[1][now_num + 1], ++ del[1][N - now_num];
		if(del[1][now_num + 1] == 2) {flag = 1; for (int i = 1; i <= N; ++ i)del[1][i] -= 2;}
		
		for (int i = 1; i <= N; ++ i)checko[i] = del[1][i];
		int olen = 2;
		for (;; ++ olen)
		{
			for (int j = 1; j <= N / 2; ++ j)
			del[olen][j] = del[olen][N - j + 1] = del[olen - 1][j * 2 - 1] + del[olen - 1][j * 2];
			del[olen][N / 2 + 1] = del[olen - 1][1] * 2;
			for (int j = 1; j <= N; ++ j) if(j != N / 2 + 1) del[olen][j] -= del[olen][N / 2 + 1];
			del[olen][N / 2 + 1] = 0;
			int flag = 1;
			for (int j = 1; j <= N; ++ j) flag &= del[olen][j] == checko[j];
			if(flag) {-- olen; break;}
//			cout << "\n\n";
		}
		for (int i = 1; i <= olen; ++ i)
		for (int j = 1; j <= N; ++ j)
		(delval[i] += m[tot][j] * del[i][j] % MOD + MOD) %= MOD;
		
		K[0] = 1; B[0] = 0;
		for (int i = 1; i <= olen; ++ i) K[i] = K[i - 1] * 2 % MOD, B[i] = 2 * (B[i - 1] + del[i][1] + MOD) % MOD;
		
		for(int i = 1; i <= q; i ++)
		{
			unsigned long long now = rd(seed) % k_max;
			long long k = now, nowans;
			if(k == 0) ans ^= (nowans = a[x]) * i ;
			else ans ^= (nowans = solve(n, N, tot, olen, x, k)) * i;
		}
		cout << ans << "\n";
	}
}
