#include <bits/stdc++.h>
using namespace std;
#define i64 long long
#define u64 unsigned long long

inline int read(void) {
    int x=0,sgn=1; char c=getchar();
    while(c< '0'||'9'< c) {(c=='-'&&(sgn=0)); c=getchar();}
    while('0'<=c&&c<='9') {x=x*10+c-'0'; c=getchar();}
    return sgn ? x : -x;
}
void write(u64 x) {
    // if(x<0) return putchar('-'),write(-x),void();
    if(x>=10) write(x/10),x%=10;
    return putchar('0'+x),void();
}

unsigned long long rd(unsigned long long &x) {
	x ^= (x << 13);
	x ^= (x >> 7);
	x ^= (x << 17);
	return x;
}

const int p=998244353;
const int inv2=499122177;

// solutions

int bruteAns[1005];
inline void brute(int n,int k_max,int x,vector <int> &a) {
    bruteAns[0]=a[x];
    int H=n>>1;
    for(int t=1; t<k_max; ++t) {
        for(int i=1; i<=H; ++i) (a[i]+=a[n+1-i])>=p && (a[i]-=p);
        for(int i=H; i>=1; --i) a[(i<<1)-1]=a[(i<<1)]=1ll*a[i]*inv2%p;
        bruteAns[t]=a[x];
    }
}

inline int getpos(int m,int x,int y) { return (x-1)*m+(y-1); }
inline void matMul(int*a,int an,int am,int*b,int bn,int bm,int* c/* Ans */) {
    #define A(x,y) (a[getpos(am,x,y)])
    #define B(x,y) (b[getpos(bm,x,y)])
    #define C(x,y) (c[getpos(bm,x,y)])
    for(int i=0; i<an*bm; ++i) c[i]=0;
    for(int i=1; i<=an; ++i) 
        for(int u=1; u<=bm; ++u) 
            for(int k=1; k<=am; ++k) 
                C(i,u)=(C(i,u)+1ll*A(i,k)*B(k,u))%p;
}
inline void matCpy(int*a,int*b,int n,int m) {  // a to b
    for(int i=0; i<n*m; ++i) a[i]=b[i];
}
int MatksmCache[6400],MatksmCache2[6400],MatksmAns[6400]; 
inline void Matksm(int* Mat,int n,int m,int a) {  // assert a>0 !!!
    if(a==1) return ; --a;
    matCpy(MatksmCache,Mat,n,m);
    matCpy(MatksmAns,Mat,n,m);
    while(1) {
        if(a&1) {
            matCpy(MatksmCache2,MatksmAns,n,m);
            matMul(MatksmCache,n,m,MatksmCache2,n,m,MatksmAns);
        }
        a>>=1;
        if(a==0) break;
        matCpy(MatksmCache2,MatksmCache,n,m);
        matMul(MatksmCache2,n,m,MatksmCache2,n,m,MatksmCache);
    }
    matCpy(Mat,MatksmAns,n,m);
}

int trans[6400],mul[6400],ini[160],ksmAns[160];

int main() {
    freopen("noodle.in","r",stdin);
    freopen("noodle.out","w",stdout);
	int test, T;
	unsigned long long seed;
	scanf("%d%d%llu", &test, &T, &seed);
	for(int Case = 1; Case <= T; Case ++) {
		int n, q, x;
		long long k_max;
		scanf("%d%d%d%lld", &n, &q, &x, &k_max);
		vector<int> a(n + 1);
		for(int i = 1; i <= n; i ++) {
			scanf("%d", &a[i]);
		}
        u64 Ans=0;
        if(n*k_max<=2e7) {
            brute(n,k_max,x,a);
            for(int i=1; i<=q; i++) {
                long long k = rd(seed) % k_max;
                Ans^=1ull*bruteAns[k]*i;
            }
        } else if((n&(-n))==n) {
            int avgMax=0,sum=0;
            for(int i=1; i<=n; ++i) (sum+=a[i])>=p && (sum-=p);
            for(int ccc=1; ccc^n; ++avgMax,ccc<<=1,sum=(sum*inv2)%p);
            brute(n,avgMax,x,a);
            for(int i=1; i<=q; i++) {
                long long k = rd(seed) % k_max;
                Ans^=1ull*( k<avgMax ? bruteAns[k] : sum)*i;
            }
        } else {
            int lowbit=(n&(-n)),loglowbit=0;
            for(int ccc=1; ccc^lowbit; ++loglowbit,ccc<<=1);
            brute(n,loglowbit+1,x,a);
            int H=((n/lowbit)+1)/2;
            for(int i=1; i<=H; ++i) ini[i-1]=a[i*lowbit*2-lowbit];
// for(int i=1; i<=H; ++i) cerr<<ini[i]<<' '; 
// cerr<<endl;
            for(int i=1,A=1,B=H; i<=H; ++i) {
                (trans[getpos(H,A,i)]+=inv2)>=p && (trans[getpos(H,A,i)]-=p);
                (trans[getpos(H,B,i)]+=inv2)>=p && (trans[getpos(H,B,i)]-=p);
                if(i&1) --B;
                else ++A;
            }
// for(int i=0; i<H*H; ++i) cerr<<trans[i]<<' '; 
// cerr<<endl;
            for(int i=1; i<=q; i++) {
                long long k = rd(seed) % k_max;
                if(k<=loglowbit) Ans^=1ull*bruteAns[k]*i;
                else {
                    matCpy(mul,trans,H,H);
                    Matksm(mul,H,H,k-loglowbit);
                    matMul(ini,1,H,mul,H,H,ksmAns);
                    Ans^=1ull*ksmAns[(x-1)/lowbit]*i;
// cerr<<"qry "<<k<<"---";
// for(int i=0; i<H; ++i) cerr<<ksmAns[i]<<' '; 
// cerr<<endl;
// for(int i=0; i<H*H; ++i) cerr<<mul[i]<<' '; 
// cerr<<endl;
// for(int i=1; i<=n; ++i) cerr<<a[i]<<' '; 
// cerr<<endl;
                }
            }
            for(int i=0; i<H*H; ++i) trans[i]=0;
        }
        write(Ans); puts("");
        continue;
	}
}