#define ssh(x)<x>
#include ssh(bits/stdc++.h)
#define rfor(x...)for(register x)
#define rep(i,l,r)rfor(ll i=l;i<=r;i++)
#define ref(i,l,r)rfor(ll i=l;i<r;i++)
#define per(i,l,r)rfor(ll i=l;i>=r;i--)
#define rev(i,u,v)rfor(ll i=head[u],v;v=to[i],i;i=next[i])
#define rej(i,s)rfor(ll i=s;i;i=(i-1)&(s))
#define red(i,n)rfor(ll i=n;i;i>>=1)
#define IO(x...)((*#x!='/'||#x[1])&&(*#x&&freopen(#x".in","r",stdin)&&freopen(#x".out","w",stdout),gc=fgc,pc=fpc,atexit(fout)))
typedef long long ll;
typedef const ll cll;
typedef unsigned long long ull;
cll N=1e6+7,mod=998244353,iv2=(mod+1)/2,iz=1<<21,oz=1<<22;
typedef ll aN[N];
char is[iz],*i1=is,*i2=is,os[oz],*o1=os,*o2=os+oz;
int fgc(){
    return i1==i2&&is==(i2=is+fread(i1=is,1,iz,stdin))?-1:*i1++;
}
void fout(){
    fwrite(os,o1-os,1,stdout),o1=os;
}
int fpc(int c){
    if(o1==o2)fout();
    return*o1++=c;
}
int(*gc)()=getchar,(*pc)(int)=putchar,wt[126];
int readchar(int l=33,int r=126){
    if(l>r)std::swap(l,r);
    int c=gc();
    for(;c<l||c>r;c=gc());
    return c;
}
ll readll(){
    ll x=0,w=1;
    int c=gc();
    for(;c<48||c>57;c=gc())c-45||(w=-w);
    for(;c>47&&c<58;c=gc())x=x*10+c-48;
    return x*w;
}
void writell(cll u,int c=32){
    int t=0;
    rfor(ull n=u<0?pc(45),0ull-u:u;n;n/=10)wt[++t]=n%10^48;
    for(t||pc(48);t;)pc(wt[t--]);
    c&&pc(c);
}
int mygets(char*s,int c=0){
    char*t=s+1;
    while((*s=gc())<33);
    while((*t=gc())>32)t++;
    c&&(*t++=c),*t=0;
    return t-s;
}
int myputs(const char*s,int c=10){
    const char*t=s;
    while(*t)pc(*t++);
    c&&pc(c);
    return t-s+(c!=0);
}
cll IO_res=IO(noodle),test=readll(),T=readll();
ull seed=readll();
unsigned long long rd(unsigned long long &x) {
	x ^= (x << 13);
	x ^= (x >> 7);
	x ^= (x << 17);
	return x;
}
aN a;
struct matrix{
    ll val[501][501];
    void merge(const matrix&a,const matrix&b,cll n){
        ll c[501][501]={};
        ref(i,0,n/2)ref(k,0,n)ref(j,0,n/2)c[i][j*2]=(c[i][j*2]+a.val[i][k]*b.val[k][j*2])%mod;
        ref(i,0,n/2)ref(j,0,n)val[i][j]=c[i][j&-2];
        ref(i,0,n/2)ref(j,0,n)val[n-i-1][j]=c[i][j&-2];
        /*ref(i,0,n)ref(k,0,n)ref(j,0,n)c[i][j]=(c[i][j]+a.val[i][k]*b.val[k][j])%mod;
        ref(i,0,n)ref(j,0,n)val[i][j]=c[i][j];*/
    }
}z[100];
struct vector{
    ll val[501];
    void merge(const vector&a,const matrix&b,cll n){
        ll c[501]={};
        ref(k,0,n)ref(j,0,n)c[j]=(c[j]+a.val[k]*b.val[k][j])%mod;
        ref(j,0,n)val[j]=c[j];
    }
};
void calc(){
    cll n=readll(),q=readll(),x=readll()-1,k_max=readll();
    ref(i,0,n)a[i]=readll();
    if(test<=3){
        cll up=test==3?21:k_max;
        ll b[up+1][n];
        ref(i,0,n)b[0][i]=a[i];
        rep(s,1,up){
            ref(i,0,n)b[s][i]=(b[s-1][i/2]+b[s-1][n-i/2-1])*iv2%mod;
        }
        ll ans=0;
        rep(i,1,q){
		    cll k=rd(seed)%k_max;
		    //printf("k=%lld\n",k);
		    //printf("%lld\n",std::min(up,k));
		    ans^=i*b[std::min(up,k)][x];
        }
        writell(ans);
        return;
    }
    if(test==4||test==5||test==6){
        memset(z[0].val,0,sizeof z[0].val);
        ref(i,0,n)z[0].val[i/2][i]=z[0].val[n-i/2-1][i]=iv2;
        //ref(i,0,n){ref(j,0,n)printf("%lld\n",z[0].val[i][j]);puts("");}
        ref(i,0,63)z[i+1].merge(z[i],z[i],n);
        ll ans=0;
        rep(i,1,q){
            ll k=rd(seed)%k_max;
            vector s;
            ref(i,0,n)s.val[i]=a[i];
            per(j,63,0)if(k>>j&1)s.merge(s,z[j],n);
		    ans^=i*s.val[x];
        }
        writell(ans);
        return;
    }//(n^2(n+q)log)
    //if(test==7||test==8||test==9){
        cll up=21;
        ll b[up+1][n];
        ref(i,0,n)b[0][i]=a[i];
        ll sz=n,dl=1;
        while(sz%2==0)sz/=2,dl*=2;
        sz*=2,dl/=2;
        rep(s,1,up){
            ref(i,0,n)b[s][i]=(b[s-1][i/2]+b[s-1][n-i/2-1])*iv2%mod;
        }
        memset(z[0].val,0,sizeof z[0].val);
        ref(i,0,sz)z[0].val[i/2][i]=z[0].val[sz-i/2-1][i]=iv2;
        //printf("%lld %lld\n",sz,dl);
        ref(i,0,63)z[i+1].merge(z[i],z[i],sz);
        ll ans=0;
        rep(i,1,q){
		    ll k=rd(seed)%k_max;
		    //printf("%lld\n",std::min(up,k));
		    ll res;
		    if(k<=up)res=b[k][x];
		    else{
		        k-=up;
		        //printf("%lld %lld %lld\n",k,x/dl,sz);
                vector s;
                ref(i,0,sz)s.val[i]=b[up][i*dl];
                per(j,63,0)if(k>>j&1)s.merge(s,z[j],sz);
                //printf("???");
		        res=s.val[x/dl];
		    }
		    ans^=i*res;
        }
        writell(ans);
    //}
}
int main(){
    rep(i,1,T)calc();
    return 0;
}//Cc!FN0I$w3ILAIKeQI?
/*
1 2 13
4 2 1 3
1 4 2 3
6 2 3 3
6 2 5 3 1 4

3 1
2
4 2 3 100000000
1 2 3 4

7 1 13
6 1 3 100
1 2 3 4 5 6

7 1 13
150 150 3 1000000000000000000
*/
