#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using db = double;

const int N = 2e6 + 5;
const ll P = 998244353;

ll qpow(ll a, ll b)
{
	ll res = 1;
	for (; b; b >>= 1, a = a * a % P)
		if (b & 1) res = res * a % P;
	return res;
}

const ll INV2 = qpow(2, P - 2);

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

ll a[N];
ll h1[505][505];
ll h[25][N];

int test, T;
unsigned long long seed;

/*
3 1 114514
16 2 7 1145141919810
1 1 4 5 1 4 1 9 1 9 8 1 0 8 9 3
*/

int n, q, x;
ll b[N];

struct Matrix
{
	ll a[155][155];
};

Matrix res, ml, tmp;

Matrix operator*(Matrix A, Matrix B)
{
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++) tmp.a[i][j] = 0;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
		{
			for (int k = 0; k < n; k++)
				tmp.a[i][j] += A.a[i][k] * B.a[k][j] % P;
			tmp.a[i][j] %= P;
		}
	return tmp;
}

void task()
{
		long long k_max;
		scanf("%d%d%d%lld", &n, &q, &x, &k_max);
	x--;
//		vector<int> a(n + 1);
	for(int i = 0; i < n; i++) 
	{
		scanf("%lld", &a[i]);
	}
	if (test == 1)
	{
		for (int i = 0; i < n; i++)
			h1[0][i] = a[i];
		for (int k = 1; k <= k_max; k++)
		{
			for (int i = 0; i < n; i++)
				h1[k][i] = (h1[k - 1][i / 2] + h1[k - 1][n - 1 - i / 2]) * INV2 % P;
		}
		ll ans = 0;
		for(int i = 1; i <= q; i ++) 
		{
			long long k = rd(seed) % k_max;
			ans ^= h1[k][x] * i;
		}
		printf("%lld\n", ans);
		return;
	}
	if (test == 2)
	{
		for (int i = 0; i < n; i++)
			h[0][i] = a[i];
		for (int k = 1; k <= k_max; k++)
		{
			for (int i = 0; i < n; i++)
				h[k][i] = (h[k - 1][i / 2] + h[k - 1][n - 1 - i / 2]) * INV2 % P;
		}
		ll ans = 0;
		for(int i = 1; i <= q; i ++) 
		{
			long long k = rd(seed) % k_max;
			ans ^= h[k][x] * i;
		}
		printf("%lld\n", ans);
		return;
	}
	if (test == 3)
	{
		ll sum = 0;
		for (int i = 0; i < n; i++)
			h[0][i] = a[i], sum = (sum + a[i]) % P;
		sum = sum * qpow(n, P - 2) % P;
		for (int k = 1; k <= 22; k++)
		{
			for (int i = 0; i < n; i++)
				h[k][i] = (h[k - 1][i / 2] + h[k - 1][n - 1 - i / 2]) * INV2 % P;
		}
		ll ans = 0;
		for(int i = 1; i <= q; i ++) 
		{
			long long k = rd(seed) % k_max;
			if (k <= 22)
				ans ^= h[k][x] * i;
			else
				ans ^= sum * i;
		}
		printf("%lld\n", ans);
		return;
	}
	ll ans = 0;
	for(int I = 1; I <= q; I ++) 
	{
		long long k = rd(seed) % k_max;
		ll co = qpow(INV2, k % (P - 1));
		/*
		Code your solution here.
		*/
		for (int j = 0; j < n; j++)
		{
			for (int i = 0; i < n; i++)
				ml.a[i][j] = res.a[i][j] = 0;
			ml.a[j / 2][j] = ml.a[n - 1 - j / 2][j] = 1;
			res.a[j][j] = 1;
		}
		for (; k; k >>= 1, ml = ml * ml)
		{
			if (k & 1) res = res * ml;
		}
		ll shi = 0;
		for (int i = 0; i < n; i++)    
		 	shi += a[i] * res.a[i][x];
		
		shi %= P;
		ans ^= co * shi % P * I;
	}
	printf("%lld\n", ans);
}

int main() 
{
	freopen("noodle.in", "r", stdin);
	freopen("noodle.out", "w", stdout);
	scanf("%d%d%llu", &test, &T, &seed);
	for(int Case = 1; Case <= T; Case ++) 
	{	
		task();
	}
	return 0;
}