#include<cstdio>
#include<vector>
using namespace std;
#define mod 998244353
char fre[20000005],*frel=fre;
#define getchar() (*frel++)
template<typename ty=int>
ty read()
{
	ty n=0;char c=getchar();
	while(c<33) c=getchar();
	while(c>32)
	{
		n=n*10+(c^48);
		c=getchar();
	}
	return n;
}
unsigned long long rd (unsigned long long &x ) {
x ^= ( x << 13 ) ;
x ^= ( x >> 7 ) ;
x ^= ( x << 17 ) ;
return x ;
}
int a[2000005];
int ans[2000005];
int use[2000005];
pair<int,int> fl[2000005];
int add(int x,int y)
{
	int z=x+y;
	return z<mod?z:z-mod;
}
void init_ans(int n,int x,unsigned long long k)
{
	int i,j,mid=n>>1;
	for(i=1;i<=n;i++)
		ans[i]=a[i];
	fl[0]={ans[x],0};
	for(i=1;i<=k+1;i++)
	{
		for(j=1;j<=mid;j++)
			ans[j]=add(ans[j],ans[n-j+1]);
		for(j=1;j<=n;j++)
			use[j]=ans[(j+1)>>1];
		for(j=1;j<=n;j++)
			ans[j]=use[j];
		fl[i]={ans[x],0};
	}
}
int init_ans2(int n,int x,unsigned long long k)
{
	int i,j,mid=n>>1,len=1,now;
	for(i=1;i<=n;i++)
		ans[i]=a[i];
	fl[0]={ans[x],0};
	for(i=1;i<=k+1&&len<n<<1;i++,len<<=1)
	{
		for(j=1;j<=mid;j++)
			ans[j]=add(ans[j],ans[n-j+1]);
		for(j=1;j<=n;j++)
			use[j]=ans[(j+1)>>1];
		for(j=1;j<=n;j++)
			ans[j]=use[j];
		fl[i]={ans[x],0};
	}
	now=i+1;
	fl[now]={ans[((x+1)>>1)],ans[n-((x+1)>>1)+1]};
	for(i=now+1;i<=k;i++)
	{
		fl[i].first=add(fl[i-1].first,fl[i-1].second);
		fl[i].second=add(fl[i-1].first,fl[i-1].first);
		if(fl[i].first==fl[i].second) break;
	}
	return i;
}
int get_pow(int n,int m)
{
	if(!m) return 1;
	int fl=get_pow(n,m>>1);fl=1ll*fl*fl%mod;
	return m&1?1ll*fl*n%mod:fl;
}
int main()
{
	freopen("noodle.in","r",stdin);
	freopen("noodle.out","w",stdout);
	fread(fre,1,sizeof(fre),stdin);
	int test=read(),T=read();
	unsigned long long seed=read<unsigned long long>();
	while(T--)
	{
		int n=read(),q=read(),x=read(),m;
		long long pr=0;
		unsigned long long k=read<unsigned long long>();
		for(int i=1;i<=n;i++)
			a[i]=read();
		if(test==0||test==1||test==2)
		{
			init_ans(n,x,k);
			for(int i=1;i<=q;i++)
			{
				unsigned long long Q=rd(seed)%k;
				pr^=1ll*i*(1ll*add(fl[Q].first,fl[Q].second)*get_pow(get_pow(2,Q),mod-2)%mod);
//				
//				printf("%d %d\n",Q,1ll*add(fl[Q].first,fl[Q].second)*get_pow(get_pow(2,Q),mod-2)%mod);
//				
			}
			printf("%lld\n",pr);
		}
		else
		{
			m=init_ans2(n,x,k);
			for(int i=1;i<=q;i++)
			{
				unsigned long long Q=rd(seed)%k;
				if(Q>m) Q=m;
				pr^=1ll*i*(1ll*add(fl[Q].first,fl[Q].second)*get_pow(get_pow(2,Q),mod-2)%mod);
//				
//				printf("%d %d\n",Q,1ll*add(fl[Q].first,fl[Q].second)*get_pow(get_pow(2,Q),mod-2)%mod);
//				
			}
			printf("%lld\n",pr);
		}
	}
	return 0;
}
/*
0 1 1242
6 5 5 100
3 6 5 9 2 4

43 499499808
95 832239070
55 970948706
7 140378117
22 166374857
3280194883

*/