#include<bits/stdc++.h>
using namespace std;
const long long skc=998244353;
long long aaa,op,_,invn,i,n,q,x,kmax,k,e,f,w,cnt,ans,now,j,u,r,p,a[2000001];
unsigned long long seed;
unsigned long long rd(unsigned long long&x){
	x^=(x<<13);
	x^=(x>>7);
	x^=(x<<17);
	return x;
}
long long pow(long long x,long long y,const long long skc){
	long long s=1;
	for(;y;y>>=1,x=x*x%skc)if(y&1)s=s*x%skc;
	return s;
}
int main(){
	ios::sync_with_stdio(0);cin.tie(0);
	freopen("noodle.in","r",stdin);
	freopen("noodle.out","w",stdout);
	cin>>op>>_>>seed;
	if(op==2||op==3){
		while(_--){
			cin>>n>>q>>x>>kmax;
			for(i=1;i<=n;i++)cin>>a[i];
			long long w=min(kmax,25ll),ans[26];
			aaa=0;
			ans[0]=a[x];
			for(i=1;i<=w;i++){
				for(j=1;j<=n/2;j++)a[j]+=a[n-j+1];
				for(j=n;j>=1;j--)a[j]=a[(j+1)/2]*499122177%skc;
				ans[i]=a[x];
			}
			for(i=1;i<=q;i++){
				k=rd(seed)%kmax;
				k=min(k,25ll);
				aaa^=ans[k]*i%skc;
			}
			cout<<aaa<<"\n";
		}
	}else while(_--){
		cin>>n>>q>>x>>kmax;
		for(i=1;i<=n;i++)cin>>a[i];
		invn=pow(n,skc-2,skc);
		aaa=0;
		for(i=1;i<=q;i++){
			k=rd(seed)%kmax;
			e=pow(2,k,skc);f=pow(e,skc-2,skc);
			w=pow(2,k,2*n);
			ans=0;now=0;
			for(j=1;j<=n;j++){
				u=a[j]*f%skc;
				r=j*w%(2*n);p=r%n;
				cnt=(j*e-p+skc)%skc*invn%skc+(r>=n?r>=2*n-x+1:r>=x);
				ans=(ans+(cnt-now)*u)%skc;
				now=cnt;
			}
			ans=(ans+skc)%skc;
			aaa^=ans*i;
		}
		cout<<aaa<<"\n";
	}
}
