#include <bits/stdc++.h>
using namespace std;
#define ull unsigned long long
#define ll long long
namespace FAST_IO
{
	#define Get getchar
	#define Put putchar
	template<typename tp=int>
	inline tp read(){tp res=0;char ch=' ';for(;ch<'0'||ch>'9';ch=Get());for(;ch>='0'&&ch<='9';ch=Get())res=(res<<3)+(res<<1)+(ch^48);return res;}
	template<typename tp>
	inline void write(tp a,char b='\n')
	{
		static int stk[21],top;
		for(top=0;a;a/=10)stk[++top]=a%10;
		for(;top;--top)Put(stk[top]^48);
		Put(b);
		return;
	}
}
using namespace FAST_IO;

ull rd(ull &x){x^=(x<<13);x^=(x>>7);x^=(x<<17);return x;}
const int N=2e6+10,mod=998244353,inv2=(mod+1)>>1;
int test,T,a[N],ans,b[N];
ull seed;
ll last_ans;
inline int add(int x){return x>=mod?x-mod:x;}
inline int sub(int x){return x<0?x+mod:x;}
#define pii pair<int,int>
#define fi first
#define se second
namespace work1{
	pii k[N];
	ll k_max;
	int n,q,x;
	void main()
	{
		for(int Case=1;Case<=T;Case++)
		{
			last_ans=0;
			n=read();q=read();x=read();k_max=read<ll>();
			for(int i=1;i<=n;++i)a[i]=add(read());
			for(int i=1;i<=q;++i)k[i].fi=rd(seed)%k_max,k[i].se=i;
			sort(k+1,k+q+1);
			for(int i=0,p=1;i<=k_max;i++)
			{
				while(p<=q&&k[p].fi==i)last_ans^=1ll*a[x]*k[p].se,p++;
				for(int i=1;i<=(n>>1);i++)b[i]=add(a[i]+a[n-i+1]);
				for(int i=1;i<=n;i++)a[i]=1ll*inv2*b[(i+1)>>1]%mod;
			}
			cout<<last_ans<<'\n';
		}
	}
	inline bool check()
	{
		int vl=a[1];
		for(int i=1;i<=n;i++)if(a[i]!=vl)return false;
		return true;
	}
	void main2()
	{
		for(int Case=1,p;Case<=T;Case++)
		{
			last_ans=0;
			n=read();q=read();x=read();k_max=read<ll>();
			for(int i=1;i<=n;++i)a[i]=add(read());
			for(int i=1;i<=q;++i)k[i].fi=rd(seed)%k_max,k[i].se=i;
			sort(k+1,k+q+1);
			p=1;
			for(int i=0;i<=k_max;i++)
			{
				while(p<=q&&k[p].fi==i)last_ans^=1ll*a[x]*k[p].se,p++;
				if(!check())
				{
					for(int i=1;i<=(n>>1);i++)b[i]=add(a[i]+a[n-i+1]);
					for(int i=1;i<=n;i++)a[i]=1ll*inv2*b[(i+1)>>1]%mod;
				}
				else break;
			}
			while(p<=q)last_ans^=1ll*a[x]*k[p].se,p++;
			cout<<last_ans<<'\n';
		}
	}
}

int main()
{
	freopen("noodle.in","r",stdin);
//	freopen("noodle.out","w",stdout);
	test=read(),T=read(),seed=read<ull>();
	if(test<=2)work1::main();
	else if(test==3)work1::main2();
//	else if(test==3)work3::main();
	else
	{
		
	}
	return 0;
}
