//test=1,2,3,4,5,6,7,8,9
//accumulate:45pts
#include <bits/stdc++.h>
#define rep(i,x,y) for(int i=x;i<y;i++)
using namespace std;
const int P = 998244353;
const int inv2 = (P + 1) / 2;
int test, T;
int n, q, x;
long long k_max;
unsigned long long seed;
unsigned long long rd(unsigned long long &x) {x ^= (x << 13);x ^= (x >> 7);x ^= (x << 17);return x;}
int b[1000002];
int add(int x, int y) { return (x + y < P) ? (x + y) : (x + y - P); }
void ad(int &x, const int &y) { x = (x + y < P) ? (x + y) : (x + y - P); }
int mul(int x, int y) { return (long long) x * y % P; }
vector<int> handle(const vector<int> &a) {
	vector<int> new_a(n + 1);
	for (int i = 1; i <= n / 2; i++) b[i] = add(a[i], a[n - i + 1]);
	for (int i = 1; i <= n; i++) new_a[i] = mul(inv2, b[(i + 1) / 2]);
	return new_a;
}
namespace solve1 {
	void main() {
		while(T--){
			cin>>n>>q>>x>>k_max;vector<int>a(n+1,0);rep(i,1,n+1)cin>>a[i];
			vector<vector<int>>handle_list={a};rep(i,1,k_max)handle_list.push_back(handle(handle_list.back()));
			unsigned long long ans=0;rep(i,1,q+1) {long long k=rd(seed) % k_max;ans^=(long long)i*handle_list[k][x];}
			cout<<ans<<"\n";
		}
	}
}
namespace solve2 {
vector<vector<int>> handle_list,trans, pw[61];vector<int> initial,segment;int cnt;
bool cmp(const vector<int> &x, const vector<int> &y) {vector<int>segment_x,segment_y;
	for(int i=1,j=1;i<=n;i=j){segment_x.push_back(i);while (j<=n&&x[i]==x[j])j++;}
	for(int i=1,j=1;i<=n;i=j){segment_y.push_back(i);while (j<=n&&y[i]==y[j])j++;}
	return segment_x==segment_y;
}
vector<vector<int>> muls(const vector<vector<int>> &x, const vector<vector<int>> &y) {
	vector<vector<int>>z(cnt,vector<int>(cnt,0));
	rep(i,0,cnt)rep(j,0,cnt)rep(k,0,cnt)ad(z[i][j],mul(x[i][k],y[k][j]));return z;
}
vector<int> mulv(const vector<int> &x, const vector<vector<int>> &y) {
	vector<int>z(cnt,0);rep(i,0,cnt)rep(j,0,cnt)ad(z[i],mul(x[j],y[j][i]));return z;
}
	int getpos(int where){return upper_bound(segment.begin(),segment.end(),where)-segment.begin()-1;}
	void sieve() {initial=handle_list.back();vector<int>nt;segment.clear();
		for(int i=1,j=1;i<=n;i=j){segment.push_back(i),nt.push_back(initial[i]);while(j<=n&&initial[i]==initial[j])j++;}
		initial=nt,cnt=segment.size();
		trans.resize(cnt);rep(i,0,cnt){trans[i].resize(cnt);rep(j,0,cnt)trans[i][j]=0;}
		rep(i,0,cnt) {
			int pos=segment[i],l=(pos+1)/2,r=n-l+1;l=getpos(l),r=getpos(r),ad(trans[l][i],inv2),ad(trans[r][i],inv2);
		}pw[0]=trans;rep(i,1,61)pw[i]=muls(pw[i-1],pw[i-1]);
	}
	int solve(long long k) {vector<int>X=initial;rep(i,0,61)if(k>>i&1)X=mulv(X, pw[i]);return X[getpos(x)];}
	void main() {
		while (T--) {
			cin>>n>>q>>x>>k_max;
			vector<int>a(n+1,0);rep(i,1,n+1)cin>>a[i];
			handle_list={a};for (;;) {vector<int>b=handle_list.back();vector<int>c=handle(b);
				if (cmp(b, c)) {break;} else {handle_list.push_back(c);}
			}int sz=handle_list.size();sieve();unsigned long long ans=0;
			rep(i,1,q+1){long long k=rd(seed)%k_max;ans^=(long long)i*((k<sz)?(handle_list[k][x]):(solve(k-sz+1)));}
			cout<<ans<<"\n";
		}
	}
}
namespace solve3{
	void main() {
		while(T--){
			cin>>n>>q>>x>>k_max;vector<int>a(n+1,0);rep(i,1,n+1)cin>>a[i];
			vector<vector<int>>handle_list={a};rep(i,1,23)handle_list.push_back(handle(handle_list.back()));
			unsigned long long ans=0;rep(i,1,q+1) {long long k=rd(seed)%k_max;ans^=(long long)i*handle_list[min(k,22LL)][x];}
			cout<<ans<<"\n";
		}
		return;
	}
}
namespace solve7{
vector<vector<int>> handle_list,trans;vector<int> initial,segment;int cnt;
bool cmp(const vector<int> &x, const vector<int> &y) {vector<int>segment_x,segment_y;
	for(int i=1,j=1;i<=n;i=j){segment_x.push_back(i);while (j<=n&&x[i]==x[j])j++;}
	for(int i=1,j=1;i<=n;i=j){segment_y.push_back(i);while (j<=n&&y[i]==y[j])j++;}
	return segment_x==segment_y;
}
vector<vector<int>> muls(const vector<vector<int>> &x, const vector<vector<int>> &y) {
	vector<vector<int>>z(cnt,vector<int>(cnt,0));
	rep(i,0,cnt)rep(j,0,cnt)rep(k,0,cnt)ad(z[i][j],mul(x[i][k],y[k][j]));return z;
}
vector<int> mulv(const vector<int> &x, const vector<vector<int>> &y) {
	vector<int>z(cnt,0);rep(i,0,cnt)rep(j,0,cnt)ad(z[i],mul(x[j],y[j][i]));return z;
}
	int getpos(int where){return upper_bound(segment.begin(),segment.end(),where)-segment.begin()-1;}
	vector<vector<int>>b0[65536],b1[65536],b2[65536],b3[65536];
	vector<vector<int>>h={{1,0},{0,1}};
	bool first=false;
	void sieve() {
		initial=handle_list.back();vector<int>nt;segment.clear();
		for(int i=1,j=1;i<=n;i=j){segment.push_back(i),nt.push_back(initial[i]);while(j<=n&&initial[i]==initial[j])j++;}
		initial=nt,cnt=segment.size();
		if(first)return;
		trans.resize(cnt);rep(i,0,cnt){trans[i].resize(cnt);rep(j,0,cnt)trans[i][j]=0;}
		rep(i,0,cnt) {
			int pos=segment[i],l=(pos+1)/2,r=n-l+1;l=getpos(l),r=getpos(r),ad(trans[l][i],inv2),ad(trans[r][i],inv2);
		}
		b0[0]=b1[0]=b2[0]=b3[0]=h;
		b0[1]=trans;rep(i,2,65536)b0[i]=muls(b0[i-1],b0[1]);
		b1[1]=muls(b0[65535],b0[1]);rep(i,2,65536)b1[i]=muls(b1[i-1],b1[1]);
		b2[1]=muls(b1[65535],b1[1]);rep(i,2,65536)b2[i]=muls(b2[i-1],b2[1]);
		b3[1]=muls(b2[65535],b2[1]);rep(i,2,65536)b3[i]=muls(b3[i-1],b3[1]);
		first=true;
	}
	int solve(long long k) {
		vector<int>X=initial;
		X=mulv(X,b3[k>>48]);X=mulv(X,b2[k>>32&65535]);X=mulv(X,b1[k>>16&65535]);X=mulv(X,b0[k&65535]);
		return X[getpos(x)];
	}
	void main() {
		while (T--) {
			cin>>n>>q>>x>>k_max;vector<int>a(n+1,0);rep(i,1,n+1)cin>>a[i];
			handle_list={a};for (;;) {vector<int>b=handle_list.back();vector<int>c=handle(b);
				if (cmp(b, c)) {break;} else {handle_list.push_back(c);}
			}int sz=handle_list.size();sieve();unsigned long long ans=0;
			rep(i,1,q+1){long long k=rd(seed)%k_max;ans^=(long long)i*((k<sz)?(handle_list[k][x]):(solve(k-sz+1)));}
			cout<<ans<<"\n";
		}
	}
}
signed main() {
	freopen("noodle.in", "r", stdin);
	freopen("noodle.out", "w", stdout);
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> test >> T >> seed;
	if (test <= 2) solve1::main();
	else if (test == 3) solve3::main();
	else if (test == 7) solve7::main();
	else solve2::main();
	return 0;
}