#include<bits/stdc++.h>
using namespace std;
#define fo(v, a, b) for(int v = a; v <= b; v++)
#define fr(v, a, b) for(int v = a; v >= b; v--)
#define cl(a, v) memset(a, v, sizeof(a))

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

typedef long long ll;

const ll P = 998244353;
const int N = 2000010;

ll power(ll a, ll x) {
	ll res = 1;
	while(x) {
		if(x & 1LL) res = res * a % P;
		a = a * a % P, x >>= 1;
	} return res;
}

const ll Inv2 = power(2, P - 2);
int n, q, x, a[N]; long long k_max, Ans;

int test, T; unsigned long long seed;

namespace Task12 {
	// brute force O(nk)
	ll res[N], b[N];
	void solve() {
		res[0] = a[x];
		fo(i,1,k_max) {
			fo(i,1,n >> 1) b[i] = (a[i] + a[n + 1 - i]) % P;
			fo(i,1,n) a[i] = Inv2 * b[(i + 1) >> 1] % P;
			res[i] = a[x];
		}
		for(int i = 1; i <= q; i++) {
			long long k = rd(seed) % k_max;
			Ans ^= i * res[k];
		}
	}
}
namespace Task3 {
	ll res[N], b[N], lim;
	void solve() {
		res[0] = a[x];
		fo(i,1,100) {
			fo(i,1,n >> 1) b[i] = (a[i] + a[n + 1 - i]) % P;
			fo(i,1,n) a[i] = Inv2 * b[(i + 1) >> 1] % P;
			res[i] = a[x], lim = i;
			fo(j,1,n) if(a[j] != a[i]) {	lim = -1; break;	}
			if(lim != -1) break;
		}
		for(int i = 1; i <= q; i++) {
			long long k = rd(seed) % k_max;
			Ans ^= (ll)i * res[min(k, lim)];
		}
	}
}

namespace Task456
{
	const int N2 = 160;
	struct mat {
		int x, y; ll a[N2][N2];
		mat() {		x = y = 0, cl(a, 0);	}
		mat operator*(const mat &temp) const {
			mat res; res.x = x, res.y = temp.y;
			fo(i,1,x) fo(k,1,y) fo(j,1,temp.y)
				res.a[i][j] = (res.a[i][j] + a[i][k] * temp.a[k][j] % P) % P;
			return res;
		}
	} A, F[100], Cur;
	void solve() {
		A.x = 1, A.y = n, F[0].x = F[0].y = n, cl(F[0].a, 0);
		fo(i,1,n) A.a[1][i] = a[i];
		fo(i,1,n) {
			int pos = (i <= (n >> 1) ? i : n + 1 - i);
			F[0].a[i][2 * pos] = Inv2, F[0].a[i][2 * pos - 1] = Inv2;
		} fo(i,1,64) F[i] = F[i - 1] * F[i - 1];
		for(int i = 1; i <= q; i++) {
			long long k = rd(seed) % k_max;
			Cur = A;
			fr(j,62,0) if(k >> j & 1LL) Cur = Cur * F[j];
			Ans ^= (ll)i * Cur.a[1][x];
		}
	}
}

namespace Task89
{
	const int N2 = 260;
	struct mat {
		int x, y; ll a[N2][N2];
		mat() {		x = y = 0, cl(a, 0);	}
		mat operator*(const mat &temp) const {
			mat res; res.x = x, res.y = temp.y;
			fo(i,1,x) fo(k,1,y) if(a[i][k]) fo(j,1,temp.y) if(temp.a[k][j])
				res.a[i][j] = (res.a[i][j] + a[i][k] * temp.a[k][j] % P) % P;
			return res;
		}
	} A, F[100], Cur;
	void solve() {
		A.x = 1, A.y = F[0].x = F[0].y = n >> 1, cl(F[0].a, 0);
		fo(i,1,n>>1) A.a[1][i] = (a[i] + a[n + 1 - i]) % P;
		fo(i,1,n>>1) {
			int pos1 = (i * 2 <= (n >> 1) ? i * 2 : n + 1 - (i * 2));
			int pos2 = (i * 2 - 1 <= (n >> 1) ? i * 2 - 1 : n + 1 - (i * 2 - 1));
			F[0].a[i][pos1] = Inv2, F[0].a[i][pos2] = Inv2;
		} fo(i,1,62) F[i] = F[i - 1] * F[i - 1];
		for(int i = 1; i <= q; i++) {
			long long k = rd(seed) % k_max;
			if(k == 0) Ans ^= (ll)i * a[x];
			else {
				Cur = A, k--;
				fr(j,62,0) if(k >> j & 1LL) Cur = Cur * F[j];
				Ans ^= (ll)i * Cur.a[1][(x + 1) >> 1] % P * Inv2 % P;
			}
		}
	}
}

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++) {
		scanf("%d%d%d%lld", &n, &q, &x, &k_max);
		for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
		
		Ans = 0;
		if(1 <= test && test <= 2) Task12 :: solve();
		else if(test == 3) Task3 :: solve();
		else if(4 <= test && test <= 6)
			Task456 :: solve();
		else if(8 <= test && test <= 9)
			Task89 :: solve();
		
		printf("%lld\n", Ans);
	}
	
	return 0;
}
