#include<bits/stdc++.h>
using namespace std;

const int N=2e6+5;
const int MOD=998244353,INV=499122177;

int ADD(int x,int y){return (x+=y)>=MOD?x-MOD:x;}
int SUB(int x,int y){return (x-=y)<0?x+MOD:x;}
int TIME(int x,int y){return (int)(1ll*x*y%MOD);}

int test;
unsigned long long seed;

int n,q,x,a[N];
long long k_max;

long long res=0;

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

namespace subtask1{

const int K=11;

int b[K][N];

int main(){
    for(int i=0;i<n;++i) b[0][i]=a[i];
    for(int j=1;j<=k_max;++j) for(int i=0;i<n;++i)
        b[j][i]=TIME(ADD(b[j-1][i>>1],b[j-1][n-(i>>1)-1]),INV);
    
    for(int i=1;i<=q;++i){
        long long k=rd(seed)%k_max;
        res^=1ll*i*b[k][x];
    }

    printf("%lld\n",res);

    return 0;
}

}

namespace subtask2{

const int N=5e2+5;

struct Matrix{int f[N][N];};
Matrix operator * (Matrix a,Matrix b){
    Matrix res={};
    for(int i=0;i<n;++i) for(int j=0;j<n;++j) for(int k=0;k<n;++k)
        res.f[i][k]=ADD(res.f[i][k],TIME(a.f[i][j],b.f[j][k]));
    return res;
}

Matrix I[60];int f[N],g[N];

int main(){
    I[0]={};
    for(int i=0;i<n;++i)
        I[0].f[i>>1][i]=INV,I[0].f[n-(i>>1)-1][i]=INV;
    for(int i=1;i<60;++i) I[i]=I[i-1]*I[i-1];

    for(int i=1;i<=q;++i){
        long long k=rd(seed)%k_max;

        int tmp=0;
        for(int c=0;c<n;++c) f[c]=(c==x);
        for(int j=0;j<60;++j) if((k>>j)&1){
            for(int c=0;c<n;++c) for(int d=0;d<n;++d)
                g[c]=ADD(g[c],TIME(I[j].f[c][d],f[d]));
            for(int c=0;c<n;++c) f[c]=g[c],g[c]=0;
        }
        for(int c=0;c<n;++c) tmp=ADD(tmp,TIME(f[c],a[c]));

        res^=1ll*i*tmp;
    }

    printf("%lld\n",res);

    return 0;
}

}

namespace subtask3{

const int N=5e3+5;
const int K=5e3+5;

int b[K][N];

int main(){
    for(int i=0;i<n;++i) b[0][i]=a[i];
    for(int j=1;j<=5000;++j) for(int i=0;i<n;++i)
        b[j][i]=TIME(ADD(b[j-1][i>>1],b[j-1][n-(i>>1)-1]),INV);
    
    for(int i=1;i<=q;++i){
        long long k=rd(seed)%k_max;
        if(k>=5000) res^=1ll*i*b[5000][x];
        else        res^=1ll*i*b[k][x];
    }

    printf("%lld\n",res);

    return 0;
}

}

namespace subtask4{

const int K=61;

int b[K][N];

int main(){
    for(int i=0;i<n;++i) b[0][i]=a[i];
    for(int j=1;j<=60;++j) for(int i=0;i<n;++i)
        b[j][i]=TIME(ADD(b[j-1][i>>1],b[j-1][n-(i>>1)-1]),INV);
    
    for(int i=1;i<=q;++i){
        long long k=rd(seed)%k_max;
        if(k>=60) res^=1ll*i*b[60][x];
        else      res^=1ll*i*b[k][x];
    }

    printf("%lld\n",res);

    return 0;
}

}

int solve(){
    res=0;

    scanf("%d%d%d%lld",&n,&q,&x,&k_max),x--;
    for(int i=0;i<n;++i) scanf("%d", &a[i]);

    if(test==2) return subtask1::main();

    if(test==1||test==4||test==5||test==6||test==8||test==9)
        return subtask2::main();

    if(test==10||test==11) return subtask3::main();

    return subtask4::main();

    return 0;
}

int main(){
    freopen("noodle.in","r",stdin);
    freopen("noodle.out","w",stdout);
    
	int T;scanf("%d%d%llu",&test,&T,&seed);

    while(T--) solve();
    return 0;
}
/*
询问的位置是固定的?
询问的轮数是随机的？
n较小的时候可以用矩阵来做？
如果是 2 的幂次的话，在 k 轮之后就固定了。

先打一波暴力看看矩阵长什么样。

存在一大堆位置是相同的，但是问题是我们要求出这个相同的位置是不方便的。

算了，我先去把其他题的暴力搞好。

怪死，矩阵打出来有很多的相同位，但是我如何去维护呢？
考虑暴力 check 出相同的位置？不行，n太大了。
*/