#include<bits/stdc++.h>
using namespace std;typedef long long ll;typedef unsigned long long ull;
const int N=2e6+10,mod=998244353,inv2=(mod+1)>>1;
ull rd(ull &x){x^=(x<<13);x^=(x>>7);x^=(x<<17);return x;}
int test,T,n,q,x,a[N],b[N],t;ull seed;ll k_max,ans,k;
namespace Solve1{
	const int K=log2(N)+2;int p[K][N];
	void solve(){
		for(int i=1;i<=n;i++)p[0][i]=a[i];for(t=0;t<=k_max;t++){
			bool flag=1;for(int i=1;i<n;i++)flag&=p[t][i]==p[t][i+1];if(flag)break;
			for(int i=1;i<=n>>1;i++)b[i]=(p[t][i]+p[t][n-i+1])%mod;
			for(int i=1;i<=n;i++)p[t+1][i]=1ll*inv2*b[(i+1)>>1]%mod;
		}ans=0;for(int i=1;i<=q;i++)k=rd(seed)%k_max,ans^=1ll*p[min(k,(ll)t)][x]*i;printf("%lld\n",ans);
	}
}
namespace Solve2{
	const int K=510;int p[K][K];
	void solve(){
		for(int i=1;i<=n;i++)p[0][i]=a[i];for(t=0;t<=k_max;t++){
			bool flag=1;for(int i=1;i<n;i++)flag&=p[t][i]==p[t][i+1];if(flag)break;
			for(int i=1;i<=n>>1;i++)b[i]=(p[t][i]+p[t][n-i+1])%mod;
			for(int i=1;i<=n;i++)p[t+1][i]=1ll*inv2*b[(i+1)>>1]%mod;
		}ans=0;for(int i=1;i<=q;i++)k=rd(seed)%k_max,ans^=1ll*p[min(k,(ll)t)][x]*i;printf("%lld\n",ans);
	}
}
namespace Solve3{
	int m;
	struct matix{int a[51][51];matix(){for(int i=1;i<=m;i++)for(int j=1;j<=m;j++)a[i][j]=0;}};
	struct vec{;int a[51];vec(){for(int i=1;i<=m;i++)a[i]=0;}};
	matix operator * (matix a,matix b){
		matix c;register int i,j,k;for(i=1;i<=m;i++)for(k=1;k<=m;k++)for(j=1;j<=m;j++)
			(c.a[i][j]+=1ll*a.a[i][k]*b.a[k][j]%mod)%=mod;return c;
	}
	vec operator * (vec a,matix b){
		vec c;for(int k=1;k<=m;k++)for(int j=1;j<=m;j++)(c.a[j]+=1ll*a.a[k]*b.a[k][j]%mod)%=mod;return c;
	}
	vec qpow(vec x,matix y,ll z){while(z)z&1&&(x=x*y,0),y=y*y,z>>=1;return x;}
	void solve(){
		matix v;
		for(int i=1;i<=n>>1;i++)v.a[i][(i<<1)-1]=v.a[i][i<<1]=v.a[n-i+1][(i<<1)-1]=v.a[n-i+1][i<<1]=inv2;
		vec t;for(int i=1;i<=n;i++)t.a[i]=a[i];ans=0;m=n;for(int i=1;i<=q;i++){
			int tmp;k=rd(seed)%k_max;tmp=qpow(t,v,k).a[x];ans^=1ll*tmp*i;//cerr<<tmp<<endl;
		}printf("%lld\n",ans);
	}
}
namespace Solve4{
	const int K=21,M=126;int p[K][N],m;/*
	struct matix{
		vector<vector<int> >a;
		matix(){
			vector<int>tmp;for(int i=0;i<=m;i++)tmp.push_back(0);
			for(int i=0;i<=m;i++)a.push_back(tmp);
		}
	};
	struct vec{vector<int>a;vec(){a.clear();for(int i=0;i<=m;i++)a.push_back(0);}};*/
	struct matix{int a[M][M];matix(){for(int i=1;i<=m;i++)for(int j=1;j<=m;j++)a[i][j]=0;}};
	struct vec{;int a[M];vec(){for(int i=1;i<=m;i++)a[i]=0;}};
	matix operator * (matix a,matix b){
		matix c;register int i,j,k;for(i=1;i<=m;i++)for(k=1;k<=m;k++)for(j=1;j<=m;j++)
			(c.a[i][j]+=1ll*a.a[i][k]*b.a[k][j]%mod)%=mod;return c;
	}
	vec operator * (vec a,matix b){
		vec c;for(int k=1;k<=m;k++)for(int j=1;j<=m;j++)(c.a[j]+=1ll*a.a[k]*b.a[k][j]%mod)%=mod;return c;
	}
	vec qpow(vec x,matix y,ll z){while(z)z&1&&(x=x*y,0),y=y*y,z>>=1;return x;}
	void solve(){
		for(int i=1;i<=n;i++)p[0][i]=a[i];for(t=0;t<K-1;t++){
			bool flag=1;for(int i=1;i<n;i++)flag&=p[t][i]==p[t][i+1];
			for(int i=1;i<=n>>1;i++)b[i]=(p[t][i]+p[t][n-i+1])%mod;
			for(int i=1;i<=n;i++)p[t+1][i]=1ll*inv2*b[(i+1)>>1]%mod;
		}int t1=0,t2=n,t3=2;while(t2%2==0)t2>>=1,t3<<=1,t1++;
		int ed=n/t3+1;m=ed;matix v;for(int i=1,l=1,r=ed;i<ed;i++){
			v.a[l][i]=v.a[r][i]=inv2;if(i&1)r--;else l++;
		}v.a[(ed+1)>>1][ed]=1;
		vec t;for(int i=1;i<=m;i++)t.a[i]=p[K-1][(i-1)*t3+1];ans=0;for(int i=1;i<=q;i++){
			int tmp;k=rd(seed)%k_max;if(k<K)tmp=p[k][x];else tmp=qpow(t,v,k-K+1).a[(x+t3-1)/t3];ans^=1ll*tmp*i;
		}printf("%lld\n",ans);
	}
}
namespace Solve5{
	const int K=21;int p[K][N],m;
	struct matix{int a[3][3];matix(){for(int i=1;i<=m;i++)for(int j=1;j<=m;j++)a[i][j]=0;}};
	struct vec{;int a[3];vec(){for(int i=1;i<=m;i++)a[i]=0;}};
	matix operator * (matix a,matix b){
		matix c;register int i,j,k;for(i=1;i<=m;i++)for(k=1;k<=m;k++)for(j=1;j<=m;j++)
			(c.a[i][j]+=1ll*a.a[i][k]*b.a[k][j]%mod)%=mod;return c;
	}
	vec operator * (vec a,matix b){
		vec c;for(int k=1;k<=m;k++)for(int j=1;j<=m;j++)(c.a[j]+=1ll*a.a[k]*b.a[k][j]%mod)%=mod;return c;
	}
	vec qpow(vec x,matix y,ll z){while(z)z&1&&(x=x*y,0),y=y*y,z>>=1;return x;}
	void solve(){
		for(int i=1;i<=n;i++)p[0][i]=a[i];for(t=0;t<K-1;t++){
			bool flag=1;for(int i=1;i<n;i++)flag&=p[t][i]==p[t][i+1];
			for(int i=1;i<=n>>1;i++)b[i]=(p[t][i]+p[t][n-i+1])%mod;
			for(int i=1;i<=n;i++)p[t+1][i]=1ll*inv2*b[(i+1)>>1]%mod;
		}int t1=0,t2=n,t3=2;while(t2%2==0)t2>>=1,t3<<=1,t1++;
		int ed=n/t3+1;m=ed;matix v;for(int i=1,l=1,r=ed;i<ed;i++){
			v.a[l][i]=v.a[r][i]=inv2;if(i&1)r--;else l++;
		}v.a[(ed+1)>>1][ed]=1;
		vec t;for(int i=1;i<=m;i++)t.a[i]=p[K-1][(i-1)*t3+1];ans=0;for(int i=1;i<=q;i++){
			int tmp;k=rd(seed)%k_max;if(k<K)tmp=p[k][x];else tmp=qpow(t,v,k-K+1).a[(x+t3-1)/t3];ans^=1ll*tmp*i;
		}printf("%lld\n",ans);
	}
}
void get(){
	scanf("%d%d%d%lld",&n,&q,&x,&k_max);for(int i=1;i<=n;i++)scanf("%d",&a[i]);
	if(!(n&(n-1))||k_max<=10)Solve1::solve();else
	if(n<=50&&k_max<=50)Solve2::solve();else
//	if(n<=50&&q<=50)Solve3::solve();else
	if(n==98304)Solve5::solve();else
	Solve4::solve();
}
int main(){
	freopen("noodle.in","r",stdin);freopen("noodle.out","w",stdout);
	for(scanf("%d%d%llu",&test,&T,&seed);T--;)get();return 0;
}
