#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N=2e6+10;const ll mod=998244353;
ll ans[2][N],rans[N],a[N];int n,x,q;ll k_max,tmpk;
unsigned long long rd(unsigned long long &x) {
	x^=(x<<13);
	x^=(x>>7);
	x^=(x<<17);
	return x;
}
ll inv2=(mod+1)/2;
unsigned long long seed;
void add(ll &x,ll y){x=(x+y)%mod;}
namespace pt10
{
	void solve()
	{
		for(int i=1;i<=n;i++)
			scanf("%lld",&a[i]),ans[0][i]=a[i];rans[0]=a[x];
		for(int i=1;i<=tmpk;i++)
		{
			for(int j=1;j<=n;j++) ans[i&1][j]=0;
			for(int j=1;j<=n;j++)
				if(j<=n/2) add(ans[i&1][j*2-1],ans[i&1^1][j]*inv2),add(ans[i&1][j*2],ans[i&1^1][j]*inv2);
				else add(ans[i&1][2*n-2*j+1],ans[i&1^1][j]*inv2),add(ans[i&1][2*n-2*j+2],ans[i&1^1][j]*inv2);
			rans[i]=ans[i&1][x];
		}
		unsigned long long ANS=0;
		for(int i=1;i<=q;i++) {
			long long k=rd(seed)%k_max;
			ANS=ANS^(rans[min((int )k,(int )tmpk)]*i);
		}
		printf("%llu\n",ANS);
	}
}
int main() {
	freopen("noodle.in","r",stdin);
	freopen("noodle.out","w",stdout);
	int test, T;
	scanf("%d%d%llu",&test,&T,&seed);
	for(int Case=1;Case<=T;Case++) {
		scanf("%d%d%d%lld",&n,&q,&x,&k_max);
		int tmp=n;tmpk=k_max;
		while(tmp%2==0)
			tmp/=2;
		if(tmp==1) {tmpk=22;pt10::solve();continue;}
		if(k_max<=500) {pt10::solve();continue;}
	}
}
