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

int n, q, x, testcount;
long long k_max;
int a[2000010];

const int mod = 998244353;
typedef long long ll;
#define int ll
inline int fastpow(int a, int n)
{
	int ans = 1;
	while(n)
	{
		if(n & 1)
			ans = ans * a % mod;
		a = a * a % mod, n >>= 1;
	}
	return ans;
}
inline int inv(int x)
{
	return fastpow(x, mod - 2);
}
const int inv2 = inv(2);
namespace Subtask1
{
	int b[2000010];
	inline int Solve(int k)
	{
		for(int i = 1; i <= n; i++)
			b[i] = a[i];
		while(k--)
		{
			for(int i = 1; i <= (n >> 1); i++)
				b[i] = (b[i] + b[n + 1 - i]) % mod;
			for(int i = n; i >= 2; i -= 2)
				b[i] = b[i - 1] = b[i >> 1] * inv2 % mod;
		}
		return b[x];
	}
}
namespace Subtask23
{
	int b[2000010][22], K;
	inline int highbit(int x)
	{
		int res = 0;
		while(x)
			res++, x >>= 1;
		return res - 1;
	}
	inline void Init()
	{
		K = (testcount == 3 ? highbit(n) : k_max);
		for(int i = 1; i <= n; i++)
			b[i][0] = a[i];
		for(int i = 1; i <= K; i++)
		{
			for(int j = 1; j <= (n >> 1); j++)
				b[j][i] = (b[j][i - 1] + b[n + 1 - j][i - 1]) % mod;
			for(int j = n; j >= 2; j -= 2)
				b[j][i] = b[j - 1][i] = b[j >> 1][i] * inv2 % mod;
//			for(int j = 1; j <= n; j++)
//				cout << b[j][i] << ' ';
//			cout << endl;
		}
	}
	inline int Solve(int k)
	{
		k = min(k, K);
//		cout << "SOLVE " << k << " = " << b[x][k] << " * " << fastpow(inv2, k) << endl;
		return b[x][k] % mod;
	}
}
namespace Subtask4
{
	struct Matrix
	{
		int a[52][52];
		Matrix(int x = 0)
		{
			memset(a, 0, sizeof(a));
			for(int i = 1; i <= n; i++)
				a[i][i] = x;
		}
		friend Matrix operator * (const Matrix &a, const Matrix &b)
		{
			Matrix ans;
			for(int i = 1; i <= n; i++)
				for(int j = 1; j <= n; j++)
					for(int k = 1; k <= n; k++)
						ans.a[i][j] = (ans.a[i][j] + a.a[i][k] * b.a[k][j]) % mod;
			return ans;
		}
	};
	Matrix BASE, ps[100];
	inline void Init()
	{
		BASE = 0;
		for(int i = 1; i <= (n >> 1); i++)
		{
			BASE.a[(i << 1) - 1][i] = inv2;
			BASE.a[(i << 1) - 1][n + 1 - i] = inv2;
			BASE.a[i << 1][i] = inv2;
			BASE.a[i << 1][n + 1 - i] = inv2;
		}
//		for(int i = 1; i <= n; i++)
//		{
//			for(int j = 1; j <= n; j++)
//				cout << BASE.a[i][j] << ' ';
//			cout << endl;
//		}
		ps[0] = BASE;
		for(int i = 1; i <= 60; i++)
			ps[i] = ps[i - 1] * ps[i - 1];
	}
	inline int Solve(int k)
	{
		Matrix ans = 1;
		for(int i = 60; i >= 0; i--)
			if((k >> i) & 1)
				ans = ans * ps[i];
//		for(int i = 1; i <= n; i++)
//		{
//			for(int j = 1; j <= n; j++)
//				cout << ans.a[i][j] << ' ';
//			cout << endl;
//		}
		int res = 0;
		for(int i = 1; i <= n; i++)
			res = (res + ans.a[x][i] * a[i]) % mod;
		return res;
	}
}
namespace Subtask7
{
	struct Matrix
	{
		int a[2][2];
		Matrix(int x = 0)
		{
			memset(a, 0, sizeof(a));
			a[0][0] = a[1][1] = x;
		}
		friend Matrix operator * (const Matrix &a, const Matrix &b)
		{
			Matrix ans;
			ans.a[0][0] = (a.a[0][0] * b.a[0][0] + a.a[0][1] * b.a[1][0]) % mod;
			ans.a[0][1] = (a.a[0][0] * b.a[0][1] + a.a[0][1] * b.a[1][1]) % mod;
			ans.a[1][0] = (a.a[1][0] * b.a[0][0] + a.a[1][1] * b.a[1][0]) % mod;
			ans.a[1][1] = (a.a[1][0] * b.a[0][1] + a.a[1][1] * b.a[1][1]) % mod;
			return ans;
		}
	};
	Matrix BASE, ps[100];
	int K = 16;
	int b[100010][22];
	inline void Init()
	{
		BASE.a[0][0] = inv2, BASE.a[0][1] = inv2, BASE.a[1][0] = 1, BASE.a[1][1] = 0;
//		for(int i = 0; i <= 1; i++)
//		{
//			for(int j = 0; j <= 1; j++)
//				cout << BASE.a[i][j] << ' ';
//			cout << endl;
//		}
		ps[0] = BASE;
		for(int i = 1; i <= 60; i++)
			ps[i] = ps[i - 1] * ps[i - 1];
		
		for(int i = 1; i <= n; i++)
			b[i][0] = a[i];
		for(int i = 1; i <= K; i++)
		{
			for(int j = 1; j <= (n >> 1); j++)
				b[j][i] = (b[j][i - 1] + b[n + 1 - j][i - 1]) % mod;
			for(int j = n; j >= 2; j -= 2)
				b[j][i] = b[j - 1][i] = b[j >> 1][i] * inv2 % mod;
//			for(int j = 1; j <= n; j++)
//				cout << b[j][i] << ' ';
//			cout << endl;
		}
	}
	inline int Solve(int k)
	{
//		cout << "QA" << endl;
		if(k <= K)
			return b[x][k];
		Matrix ans = 1;
		for(int i = 60; i >= 0; i--)
			if(((k - K) >> i) & 1)
				ans = ans * ps[i];
		int res1 = b[1][K], res2 = b[n][K];
		if(x <= 65536)
			return (res1 * ans.a[0][0] + res2 * ans.a[0][1]) % mod;
		else
			return (res1 * ans.a[1][0] + res2 * ans.a[1][1]) % mod;
	}
}
#undef int

inline int Solve(int k)
{
	if(testcount == 1)
		return Subtask1 :: Solve(k);
	else if(testcount == 2 || testcount == 3)
		return Subtask23 :: Solve(k);
	else if(testcount == 4)
		return Subtask4 :: Solve(k);
	else if(testcount == 7)
		return Subtask7 :: Solve(k);
	return -1;
}

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

int main() {
	freopen("noodle.in", "r", stdin);
	freopen("noodle.out", "w", stdout);
	int T;
	unsigned long long seed;
	scanf("%d %d %llu", &testcount, &T, &seed);
	for(int Case = 1; Case <= T; Case ++) {
		scanf("%d %d %d %lld", &n, &q, &x, &k_max);
		for(int i = 1; i <= n; i ++) {
			scanf("%d", &a[i]);
		}
		if(testcount == 2 || testcount == 3)
			Subtask23 :: Init();
		else if(testcount == 4)
			Subtask4 :: Init();
		else if(testcount == 7)
			Subtask7 :: Init();
		ll xorans = 0;
		for(int i = 1; i <= q; i++) {
			long long k = rd(seed) % k_max;
//			printf("K = %lld, ", k);
			int ans = Solve(k);
//			printf("ANS = %d\n", ans);
			xorans ^= (1ll * ans * i);
		}
		printf("%lld\n", xorans);
	}
}
