#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define mt make_tuple
#define pc putchar
#define chkmx(a,b) (a)=max((a),(b))
#define chkmn(a,b) (a)=min((a),(b))
#define lowbit(x) ((x)&-(x))
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
template<class T>void read(T&x){x=0;char c=getchar();bool f=false;for(;!isdigit(c);c=getchar())f|=(c=='-');for(;isdigit(c);c=getchar())x=x*10+(c-'0');if(f)x=-x;}
template<class T,class ...Arg>void read(T&x,Arg&...arg){read(x);read(arg...);}
template<class T>void write(T x){if(x<0)pc('-'),x=-x;if(x>=10)write(x/10);pc(x%10+'0');}
template<class T,class ...Arg>void write(T x,Arg ...arg){write(x);pc(' ');write(arg...);}
template<class ...Arg>void writeln(Arg ...arg){write(arg...);pc('\n');}
const int mod=998244353;
const int N=2e6+10,Q=5e7+10;
struct mint{
	int x;
	mint(int o=0){x=o%mod;}
	mint&operator+=(mint b){return x+=b.x,(x>=mod&&(x-=mod)),*this;}
	mint&operator-=(mint b){return x-=b.x,(x<0&&(x+=mod)),*this;}
	mint&operator*=(mint b){return(x=1ll*x*b.x%mod),*this;}
	mint&operator^=( int b){mint a=*this;x=1;while(b)(b&1)&&(*this*=a,1),a*=a,b>>=1;return*this;}
	mint&operator/=(mint b){return*this*=(b^=mod-2);}
	friend mint operator+(mint a,mint b){return a+=b;}
	friend mint operator-(mint a,mint b){return a-=b;}
	friend mint operator*(mint a,mint b){return a*=b;}
	friend mint operator^(mint a, int b){return a^=b;}
	friend mint operator/(mint a,mint b){return a/=b;}
	mint operator-(){return 0-*this;}
};
/*namespace solvetest{
	const int N=48;
	struct mat{
		ll a[N][N];
		mat(){memset(a,0,sizeof a);}
		ll*operator[](int x){return a[x];}
		mat operator*(mat b){
			mat c;
			for(int i=0;i<N;i++)
				for(int j=0;j<N;j++)
					for(int k=0;k<N;k++)
						c[i][k]+=a[i][j]*b[j][k];
			return c;
		}
		ll print(){
			ll mn;memset(&mn,0x3f,sizeof(ll));
			for(int i=0;i<N;i++)for(int j=0;j<N;j++)chkmn(mn,a[i][j]);
			printf("min:%lld\n",mn);
			for(int i=0;i<N;i++,pc('\n'))
				for(int j=0;j<N;j++)
					if(a[i][j]-mn)printf("%lld ",a[i][j]-mn);
					else printf("  ");
			return mn;
		}
	}a,b;
	void work(){
		for(int i=0;i<N;i++)a[i][i]=1;
		for(int i=0;i<N;i++)b[i/2][i]=b[N-i/2-1][i]=1;
		ll lst=0;
		for(int i=1;i<40;i++){
			a=a*b;
			ll now=a.print();
			write(i);pc(' ');
			if(lst*2==now)puts("*2");
			else if(lst*2+2==now)puts("*2+2");
			else puts("UK");
			lst=now;
		}
	}
}*/
namespace solvetest1{
	const int N=98304;
	void work(){
		map<int,ll>tmp;
		tmp[5]=1;
		for(int i=1;i<=20;i++){
			map<int,ll>nw;
			for(auto X:tmp)nw[(X.fi+1)/2]+=X.se,nw[(X.fi+N+1)/2]+=X.se;
			ll mn=0x3f3f3f3f3f3f3f3f;for(auto X:nw)chkmn(mn,X.se);
			printf("%d min:%lld\n",i,mn);
			//for(auto X:nw)pc('('),write(X.fi,X.se-mn),pc(')'),pc(' ');pc('\n');
			swap(nw,tmp);
		}
	}
}
ull rd(ull&x){x^=(x<<13);x^=(x>>7);x^=(x<<17);return x;}
int test,T;ull seed;
int n,q,x;ll kmx;
mint a[N];ll k[N];
const mint inv2=(mod+1)/2;
namespace solve0{
	mint b[N];vector<int>id[N];
	void work(){
		ll ans=0;
		for(int i=0;i<=kmx;i++)id[i].clear();
		for(int i=1;i<=q;i++)id[k[i]].pb(i);
		for(int c=0;c<kmx;c++){
			for(auto i:id[c])ans^=(1ll*i*a[x].x);
			for(int i=1;i<=n/2;i++)b[i]=a[i]+a[n-i+1];
			for(int i=1;i<=n;i++)a[i]=b[(i+1)/2]*inv2;
			//for(int i=1;i<=n;i++)write(a[i].x),pc(' ');pc('\n');
		}
		writeln(ans);
	}
}
namespace solve1{
	const int N=153;
	struct mat{
		int n,m;
		mint a[N][N];
		mat(int n=0,int m=0):n(n),m(m){memset(a,0,sizeof a);}
		mint*operator[](int x){return a[x];}
	}tmp;
	void mul(mat&c,mat&a,mat&b){
		memset(tmp.a,0,sizeof tmp.a);
		tmp.n=a.n,tmp.m=b.m;assert(a.m==b.n);
		for(int i=1;i<=a.n;i++)
			for(int j=1;j<=a.m;j++)
				for(int k=1;k<=b.m;k++)
					tmp[i][k]+=a[i][j]*b[j][k];
		swap(tmp,c);
	}
	const int M=61;
	mat f[M],it,res;
	void work(){
		memset(f,0,sizeof f);
		f[0].n=f[0].m=n;
		for(int i=1;i<=n;i++)f[0][i][(i+1)/2]=f[0][i][(i+1+n)/2]=inv2;
		for(int i=1;i<M;i++)mul(f[i],f[i-1],f[i-1]);
		it.n=1,it.m=n;memset(it.a,0,sizeof it.a);it[1][(x+1)/2]=it[1][n-(x+1)/2+1]=inv2;
		ll ot=0;
		for(int i=1;i<=q;i++){
			if(k[i]==0){ot^=(1ll*a[x].x*i);continue;}
			k[i]--;
			res=it;
			for(int j=M-1;~j;j--)if(k[i]>>j&1)mul(res,res,f[j]);
			mint ans=0;
			for(int j=1;j<=n;j++)ans+=res[1][j]*a[j];
			//for(int j=1;j<=n;j++)write(res[1][j].x),pc(' ');pc('\n');
			ot^=(1ll*ans.x*i);
		}
		writeln(ot);
	}
}
namespace solve2{
	bool ban[Q];
	const int K=30;
	map<int,ll>coef[K];
	mint ans[Q];
	void trans(int i){
		for(auto X:coef[i])
			coef[i+1][(X.fi+1)/2]+=X.se,
			coef[i+1][(X.fi+1+n)/2]+=X.se;
	}
	mint val[N],sum;
	struct mat{
		mint a,b;
		mat();
		mat(mint a,mint b):a(a),b(b){}
		mat operator*(mat rhs){
			return mat(a*rhs.a,b*rhs.a+rhs.b);
		}
	};
	mint kkk(ll b){
		mat res=mat(1,0),a=mat(4,1);
		while(b){
			if(b&1)res=res*a;
			a=a*a;b>>=1;
		}
		return res.a+res.b;
	}
	mint jisuan(ll k){
		if(k%2==0)return 2*kkk((k-17)/2);
		else return kkk((k-17)/2);
	}
	mint calc(ll k){
		if(k<=19)return val[k];
		if(k&1) return val[19]+(jisuan(k)-5)*sum;
		else return val[18]+(jisuan(k)-2)*sum;
	}
	void calc(int x){
		for(int i=0;i<30;i++)coef[i].clear();
		coef[0][x]=1;
		for(int i=1;i<=19;i++)trans(i-1);
		for(int i=0;i<=19;i++){
			val[i]=0;
			for(auto X:coef[i])val[i]+=X.se*a[X.fi];
		}
		sum=0;for(int i=1;i<=n;i++)sum+=a[i];
		for(int i=1;i<=q;i++)if(!ban[i]){
			//if(i%1000==0)cerr<<i<<endl;
			ans[i]+=calc(k[i]);
		}
	}
	void work(){
		//找出系数的循环节与变化量
		//首先操作
		ll ot=0;
		memset(ban,0,sizeof ban);
		memset(ans,0,sizeof ans);
		for(int i=1;i<=q;i++)if(k[i]==0)ban[i]=1,ot^=(1ll*i*a[x].x);else k[i]--;
		calc((x+1)/2);
		calc(n-(x+1)/2+1);
		for(int i=1;i<=q;i++)if(!ban[i]){
			ans[i]*=(inv2^((k[i]+1)%(mod-1)));
			ot^=(1ll*i*ans[i].x);
		}
		writeln(ot);
	}
}
signed main(){
	freopen("noodle.in","r",stdin);
	freopen("noodle.out","w",stdout);
	read(test,T,seed);
	for(int Case=1;Case<=T;Case++) {
		read(n,q,x,kmx);
		for(int i=1;i<=n;i++)read(a[i]);
		for(int i=1;i<=q;i++)k[i]=rd(seed)%kmx;
		if(n==lowbit(n)){kmx=31;for(int i=1;i<=q;i++)chkmn(k[i],30ll);}
		if((n<=500&&q<=500&&kmx<=500)||kmx<=50)solve0::work();
		else if(n<=150&&q<=150)solve1::work();
		else if(n==98304)solve2::work();
	}
	//cerr<<1.*clock()/CLOCKS_PER_SEC<<endl;
	return 0;
}
