/*
after dusk passed,
there is a starry sky.
*/
#include <bits/stdc++.h>
#define m_k make_pair
#define inf 0x3f3f3f3f
#define mod 998244353
#define int long long
#define len(a) (int)a.size()
using namespace std;
const int N=2*1e6+100,iv=(mod+1)/2;
int n,q,x,kmax,v[N];
unsigned long long seed;
inline void add(int &a,int b){a=((a+b>=mod)?a+b-mod:a+b);}
inline void del(int &a,int b){a=((a-b<0)?a-b+mod:a-b);}
inline void mul(int &a,int b){a=a*b%mod;}
inline int m_pow(int a,int b)
{
	int ans=1;
	while (b)
	{
		if (b&1) mul(ans,a);
		b>>=1;
		mul(a,a);
	}
	return ans;
}
inline int read()
{
	int f=1,x=0;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
	return x*f;
}
void write(int x)
{
	if (x>=10) write(x/10);
	putchar('0'+x%10);
}
unsigned long long rd ( unsigned long long &x )
{
	x ^= ( x << 13 ) ;
	x ^= ( x >> 7) ;
	x ^= ( x << 17 ) ;
	return x ;
}
namespace subtask1
{
	vector <int> f[550];
	int tmp[N];
	void solve()
	{
		for (int i=0;i<=kmax;i++) f[i].resize(n+1);
		for (int i=1;i<=n;i++) f[0][i]=v[i];
		for (int i=1;i<=kmax;i++)
		{
			int lim=n/2;
			for (int j=1;j<=lim;j++) tmp[j]=f[i-1][j],add(tmp[j],f[i-1][n-j+1]),mul(tmp[j],iv);
			for (int j=1;j<=n;j++) f[i][j]=tmp[(j+1)>>1];
		}
		int ans=0;
		for (int i=1;i<=q;i++)
		{
			int k=rd(seed)%kmax;
			ans^=f[k][x]*i;
		}
		write(ans);putchar('\n');
	}
}
struct matrix
{
	int n,a[510][510];
	void clear(){for(int i=1;i<=n;i++)memset(a[i],0,(n+10)*sizeof(int));}
	void init(){for(int i=1;i<=n;i++) a[i][i]=1;}
}tr[61];
struct Vector
{
	int n,a[510];
	void clear(){memset(a,0,sizeof(a));}
};
matrix operator *(matrix a,matrix b)
{
	static matrix ans;
	ans.n=a.n;ans.clear();
	for (int i=1;i<=a.n;i++)
	{
		for (int k=1;k<=a.n;k++)
		{
			int now=a.a[i][k];
			for (int j=1;j<=a.n;j++) add(ans.a[i][j],now*b.a[k][j]%mod);
		}
	}
	return ans;
}
int ret=0;
Vector operator *(Vector a,matrix b)
{
	static __int128 tmp[510];
	for (int i=1;i<=a.n;i++) tmp[i]=0; 
	for (int j=1;j<=a.n;j++)
	{
		for (int i=1;i<=a.n;i++) tmp[i]+=a.a[j]*b.a[j][i];
	}
	for (int i=1;i<=a.n;i++) a.a[i]=tmp[i]%mod;
	return a;
}
matrix operator ^(matrix a,int b)
{
	static matrix ans;
	ans.n=a.n;ans.clear();ans.init();
	while (b)
	{
		if (b&1) ans=ans*a;
		b>>=1;
		a=a*a;
	}
	return ans;
}
namespace subtask2
{
	int a[N],w,l[N],r[N],cnt,id[N],tmp[N];
	pair <int,int> b[N],c[N];
	vector <int> f[31];
	void solve()
	{
		for (int i=1;i<=n;i++) a[i]=i;
		for (int ti=1;ti<=25;ti++)
		{
			for (int i=1;i<=n/2;i++)
			{
				if (a[i]<=a[n-i+1]) b[i]=m_k(a[i],a[n-i+1]);
				else b[i]=m_k(a[n-i+1],a[i]);
			}
			w=0;
			for (int i=1;i<=n/2;i++) c[++w]=b[i];
			sort(c+1,c+1+w);w=unique(c+1,c+1+w)-c-1;
			for (int i=1;i<=n;i++)
			{
				int pos=lower_bound(c+1,c+1+w,b[(i+1)/2])-c;
				a[i]=pos;
			}
		}
		for (int i=0;i<=25;i++) f[i].resize(n+1);
		for (int i=1;i<=n;i++) f[0][i]=v[i];
		for (int i=1;i<=25;i++)
		{
			int lim=n/2;
			for (int j=1;j<=lim;j++) tmp[j]=f[i-1][j],add(tmp[j],f[i-1][n-j+1]),mul(tmp[j],iv);
			for (int j=1;j<=n;j++) f[i][j]=tmp[(j+1)>>1];
		}
		cnt=0;
		for (int i=1;i<=n;)
		{
			int j=i;
			while (j<=n&&a[i]==a[j]) j++;
			fill(id+i,id+j,++cnt);
			l[cnt]=i;r[cnt]=j-1;
			i=j;
		}
		for (int i=0;i<60;i++)
		{
			if ((1ll<<i)>kmax) break;
			tr[i].n=cnt;tr[i].clear();
		}
		for (int i=1;i<=cnt;i++)
		{
			assert(l[i]%2==1);
			int to=(l[i]+1)/2;
			add(tr[0].a[id[to]][i],iv);
			add(tr[0].a[id[n-to+1]][i],iv);
		}
		for (int i=1;i<60;i++)
		{
			if ((1ll<<i)>kmax) break;
			tr[i]=tr[i-1]*tr[i-1];
		}
		int ans=0;Vector F;F.n=n;F.clear();
		for (int t=1;t<=q;t++)
		{
			int k=rd(seed)%kmax;
			if (k<=25)
			{
				ans^=f[k][x]*t;
				continue;
			}
			k-=25;F.n=cnt;
			for (int i=1;i<=cnt;i++) F.a[i]=f[25][l[i]];
			for (int i=0;i<60;i++) if (k>>i&1) F=F*tr[i];
			ans^=F.a[id[x]]*t;
		}
		printf("%lld\n",ans);
	}
}
namespace subtask3
{
	int tmp[N];
	vector <int> f[31];
	void solve()
	{
		for (int i=0;i<=25;i++) f[i].resize(n+1);
		for (int i=1;i<=n;i++) f[0][i]=v[i];
		for (int i=1;i<=25;i++)
		{
			int lim=n/2;
			for (int j=1;j<=lim;j++) tmp[j]=f[i-1][j],add(tmp[j],f[i-1][n-j+1]),mul(tmp[j],iv);
			for (int j=1;j<=n;j++) f[i][j]=tmp[(j+1)>>1];
		}
		int sum=0,ans=0;
		for (int t=1;t<=q;t++)
		{
			int k=rd(seed)%kmax;
			int now=min(25ll,k);
			ans^=f[now][x]*t;
		}
		printf("%lld\n",ans);
	}
}
signed main()
{
	freopen("noodle.in","r",stdin);
	freopen("noodle.out","w",stdout);
	int tp=read(),T=read();
	scanf("%llu",&seed);
	while (T--)
	{
		n=read();q=read();x=read();kmax=read();
		for (int i=1;i<=n;i++) v[i]=read();
		if (kmax<=510)
		{
			subtask1::solve();
			continue;
		}
		if (__builtin_popcount(n)==1)
		{
			subtask3::solve();
			continue;
		}
		subtask2::solve();
	}
}