#include<bits/stdc++.h>
using namespace std;
#define ll long long
inline int read()
{
	char ch=getchar(); int ne=0; while(!isdigit(ch)) {if(ch=='-') ne=1; ch=getchar();}
	int ans=0; while(isdigit(ch)) ans=ans*10+ch-'0',ch=getchar();
	if(ne) return -ans;
	else return ans;
}
#define mod 998244353
inline int add(int x,int y) {return x+y>=mod?x+y-mod:x+y;}
inline int sub(int x,int y) {return x-y<0?x-y+mod:x-y;}
inline int mul(int x,int y) {return 1LL*x*y%mod;}
inline int add(int x,int y,int z) {return add(add(x,y),z);}
inline int mul(int x,int y,int z) {return mul(mul(x,y),z);}
int qpow(int x,ll y)
{
	int ans=1;
	while(y)
	{
		if(y&1) ans=mul(ans,x);
		x=mul(x,x),y>>=1;
	}
	return ans;
}
int Inv(int x) {return qpow(x,mod-2);}
unsigned long long _seed;
unsigned long long rd(unsigned long long &x) {
	x ^= (x << 13);
	x ^= (x >> 7);
	x ^= (x << 17);
	return x;
}
#define N 2000005
const int i2=(mod+1)/2;
int a[N],b[N],n,Q,x;
struct Query{ll v; int id;};
Query q[N];
bool cmp(Query x,Query y) {return x.v<y.v;}
void trans()
{
	for(int i=1;i<=n/2;i++) b[i]=add(a[i],a[n-i+1]);
	for(int i=1;i<=n/2;i++) a[i*2-1]=a[i*2]=b[i];
}
void work()
{
	long long k_max;
	cin>>n>>Q>>x>>k_max;
	for(int i=1;i<=n;i++) a[i]=read();
	for(int i=1;i<=Q;i++)
	{
		long long k = rd(_seed) % k_max;
		q[i].id=i,q[i].v=k;
	}
	sort(q+1,q+Q+1,cmp);
	int cur=1,ipw=1;
	ll ans=0;
	for(int i=0;i<k_max;i++)
	{
		int res=mul(a[x],ipw);
		while(cur<=Q&&q[cur].v==i) ans^=1LL*q[cur].id*res,cur++;
		trans(); ipw=mul(ipw,i2);
	}
	printf("%lld\n",ans);
}
namespace Mat
{
	const int M=155;
	struct Mat
	{
		int a[M][M];
		Mat() {memset(a,0,sizeof(a));}
	};
	int siz;
	Mat operator * (Mat x,Mat y)
	{
		Mat ans;
		for(int i=1;i<=siz;i++) for(int k=1;k<=siz;k++) for(int j=1;j<=siz;j++) ans.a[i][j]=add(ans.a[i][j],mul(x.a[i][k],y.a[k][j]));
		return ans;
	}
	Mat tr[65];
	int tmp[M],res[M];
	void Main()
	{
		long long k_max;
		cin>>n>>Q>>x>>k_max;
		for(int i=1;i<=n;i++) a[i]=read();
		for(int i=1;i<=Q;i++)
		{
			long long k = rd(_seed) % k_max;
			q[i].id=i,q[i].v=k;
		}
		sort(q+1,q+Q+1,cmp);
		int cur=1,ipw=1;
		ll ans=0; int ned=1,t=n;
		while(t%2==0) t/=2,ned++;
		for(int i=0;i<ned;i++)
		{
			int res=mul(a[x],ipw);
			while(cur<=Q&&q[cur].v==i) ans^=1LL*q[cur].id*res,cur++;
			trans(); ipw=mul(ipw,i2);
		}
//		printf("%d %d\n",cur,ned);
		int len=n/t; siz=t/2+1;
		int x=1,y=siz;
		for(int i=0;i<60;i++) memset(tr[i].a,0,sizeof(tr[i].a));
		for(int i=1;i<=siz;i++)
		{
			tr[0].a[i][x]++;
			tr[0].a[i][y]++;
			if(i%2==1) y--;
			if(i%2==0) x++;
		}
//		for(int i=1;i<=siz;i++) for(int j=1;j<=siz;j++) printf("%d%c",tr[0].a[i][j]," \n"[j==siz]);
		for(int i=1;i<60;i++) tr[i]=tr[i-1]*tr[i-1];
		for(int i=cur;i<=Q;i++)
		{
			ll go=q[i].v-ned;
			for(int j=1;j<=siz;j++)
			{
//				printf("%d%c",(j-1)*len*2+1," \n"[j==siz]);
				tmp[j]=a[(j-1)*len*2+1];
			}
			for(int j=0;j<60;j++) if(go>>j&1)
			{
				memset(res,0,sizeof(res));
				for(int c=1;c<=siz;c++) for(int d=1;d<=siz;d++) res[d]=add(res[d],mul(tmp[c],tr[j].a[c][d]));
				memcpy(tmp,res,sizeof(tmp));
			}
			int id=(x-1)/(len*2)+1;
			tmp[id]=mul(tmp[id],qpow(i2,q[i].v));
//			printf("%d %d : %d\n",q[i].id,q[i].v,tmp[id]);
			ans^=1LL*q[i].id*tmp[id];
		}
		printf("%lld\n",ans);
	}
};
signed main() {
	freopen("noodle.in","r",stdin);
	freopen("noodle.out","w",stdout);
	int test, T;
	scanf("%d%d%llu", &test, &T, &_seed);
	if(test<=2)
	{
		for(int Case = 1; Case <= T; Case ++) work();
	}
	else
	{
		for(int Case = 1; Case <= T; Case ++) Mat::Main();
	}
}
