// Fresh Peach Heart Shower
#include <bits/stdc++.h>
#define pb push_back
#define mem(x,y) memset(x,y,sizeof(x))
#define MP std::make_pair
#define ALL(x) (x).begin(),(x).end()
#define ln std::putchar('\n')
#define lsp std::putchar(' ')
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,b,a) for(int i=(b);i>=(a);--i)
#define dprintf(x...) fprintf(stderr,x)
typedef std::pair<int,int> pii;
typedef std::vector<int> poly;
template <class t> inline void read(t &s)
{
	s=0;
	char c=getchar();
	signed f=0;
	while(!isdigit(c))f|=c=='-',c=getchar();
	while(isdigit(c))s=(s<<3)+(s<<1)+(c^48),c=getchar();
	if(f)s=-s;
}
template <class t> inline void write(t x)
{
	if(!x)return std::putchar('0'),void();
	if(x<0)std::putchar('-'),x=-x;
	static signed st[50],tp=0;
	while(x)st[++tp]=x%10,x/=10;
	while(tp)std::putchar(st[tp--]^48);
}
inline void setIn(std::string s){freopen(s.c_str(),"r",stdin);}
inline void setOut(std::string s){freopen(s.c_str(),"w",stdout);}
inline void setIO(std::string s){setIn(s+".in"),setOut(s+".out");}
template <class t> inline bool ckmin(t&x,t y){if(x>y)return x=y,1;return 0;}
template <class t> inline bool ckmax(t&x,t y){if(x<y)return x=y,1;return 0;}
inline int lowbit(int x){return x&(-x);}
inline unsigned long long rd(unsigned long long &x) {
	x ^= (x << 13);
	x ^= (x >> 7);
	x ^= (x << 17);
	return x;
}
const int MaxN=2e6+50;
const int p=998244353;
const int inv2=(p+1)/2;
unsigned long long seed;
inline int fpow(int a,int b)
{
	int ret=1;
	for(;b;b>>=1,a=1LL*a*a%p)if(b&1)ret=1LL*ret*a%p;
	return ret;
}
int N;
struct Mat
{
	std::vector<poly > a;
	inline void init(){a=std::vector<poly >(N,poly(N));}
	inline Mat operator * (const Mat &nt) const
	{
		Mat ret;ret.init();
		rep(i,0,N-1)rep(k,0,N-1)rep(j,0,N-1)ret.a[i][j]=(ret.a[i][j]+1LL*a[i][k]*nt.a[k][j])%p;
		return ret;
	}
}pw[65];
inline Mat fpow(Mat a,int b)
{
	Mat ret;ret.init();
	rep(i,0,N-1)ret.a[i][i]=1;
	for(;b;b>>=1,a=a*a)if(b&1)ret=ret*a;
	return ret;
}
inline long long mylg(long long x){return 63-__builtin_clzll(x);}
int a[MaxN],b[MaxN],A[24][MaxN];
int n,q,Rdv;
inline void go()
{
	rep(i,1,n/2)b[i]=(a[i]+a[n-i+1])%p;
	rep(i,1,n)a[i]=1LL*b[(i+1)/2]*inv2%p;
}
std::mt19937 rnd(time(0));
struct Node
{
	int l,r;
	inline bool operator < (const Node &nt) const
	{
		return l<nt.l;
	}
};
struct Vec
{
	poly a;
	inline void init(){a=poly(N);}
	inline Vec operator * (const Mat &nt) const
	{
		Vec ret;ret.init();
		rep(i,0,N-1)rep(k,0,N-1)ret.a[k]=(ret.a[k]+1LL*a[i]*nt.a[i][k])%p;
		return ret;
	}
};
std::vector<Node > F;
int x;
long long k_max;
inline void BF()
{
	dprintf("bf\n");
	rep(i,1,n)read(a[i]),A[0][i]=a[i];
	rep(i,1,k_max)go(),std::memcpy(A[i],a,sizeof(int)*(n+5));
	long long Answer=0;
	for(int i = 1; i <= q; i ++) {
//		if(!(i%1000))dprintf("i %d\n",i);
		long long k = rd(seed) % k_max;
		long long w=A[k][x];
//		dprintf("Resu %lld\n",w);
		Answer^=w*i;
	}
	dprintf("XorAnswer %lld\n",Answer);
	write(Answer),ln;
}
inline void work()
{
//	dprintf("work\n");
	read(n),read(q),read(x),read(k_max);
	if(k_max<=10)return BF();
	rep(i,1,n)a[i]=rnd()%p;
	int lstct=-1;
	rep(w,0,40)
	{
		int lp=1,ct=0,lst=-1;
		rep(i,1,n)if(lst!=a[i])++ct,lst=a[i],lp=i;
		if(ct==lstct)
		{
			Rdv=w;
			N=ct;
			F.resize(N);
			lp=1,ct=0,lst=-1;
			rep(i,1,n)if(lst!=a[i])
			{
				if(i>1)F[ct]=(Node){lp,i-1},++ct;
				lst=a[i],lp=i;
			}
			F[ct]=(Node){lp,n};
			break;
		}
		lstct=ct,go();
	}
//	dprintf("Rdv %d\n",Rdv);
	rep(i,1,n)read(a[i]),A[0][i]=a[i];
	rep(i,1,Rdv)go(),std::memcpy(A[i],a,sizeof(int)*(n+5));
	Mat base;base.init();
	auto getpos=[&](int x)->int{return std::upper_bound(ALL(F),(Node){x,0})-F.begin()-1;};
	dprintf("N %d\n",N);
	rep(i,0,N-1)
	{
//		dprintf("F %d lr %d %d\n",i,F[i].l,F[i].r);
		std::multiset<int> to;
		rep(j,F[i].l,F[i].l)
//		rep(j,F[i].l,F[i].r)
		{
			std::multiset<int> cur;
			cur.insert(getpos((j+1)/2));
			cur.insert(getpos(n-(j+1)/2+1));
			if(!to.size())to=cur;
//			else assert(to==cur);
		}
		for(auto j:to)(base.a[j][i]+=inv2)%=p;
	}
//	dprintf("Rdv %d\n",Rdv);
	int lgk=mylg(k_max);
	pw[0]=base;
//	dprintf("lgk %d\n",lgk);
	rep(i,1,lgk)dprintf("wh %d\n",i),pw[i]=pw[i-1]*pw[i-1];
//	dprintf("pwok");
	Vec st;st.init();
	rep(i,0,N-1)st.a[i]=a[F[i].l];
	int whx=getpos(x);
	auto solve=[&](long long k)->int
	{
		if(k<=Rdv)return A[k][x];
//		dprintf("bigask\n");
		long long rem=k-Rdv;
		Vec ret=st;
		per(i,lgk,0)if(rem>>i&1)ret=ret*pw[i];
		return ret.a[whx];
	};
	dprintf("q %d\n",q);
	long long Answer=0;
	for(int i = 1; i <= q; i ++) {
//		if(!(i%1000))dprintf("i %d\n",i);
		long long k = rd(seed) % k_max;
		long long w=solve(k);
//		dprintf("Resu %lld\n",w);
		Answer^=w*i;
	}
	dprintf("XorAnswer %lld\n",Answer);
	write(Answer),ln;
}
signed main(void)
{
	setIO("noodle");

	int test, T;
	scanf("%d%d%llu", &test, &T, &seed);
	for(int Case = 1; Case <= T; Case ++) work();
	return 0;
}



