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

typedef long long int64;
typedef unsigned long long uint64;

template<class T,class T2,T mod>
struct modint{
  
  using mint=modint;
  using type=T;
  using type2=T2;
  
  static type umod(){return mod;}
  
  type v;
  
  modint():v(){}
  modint(const type &_v):v(_v){}
  
  template<class input_type>
  static mint standard(input_type v){return mint((v%mod+mod)%mod);}
  
  explicit operator bool ()const{return v;}
  bool operator ! ()const{return !v;}
  
  friend bool operator == (const mint &a,const mint &b){return a.v==b.v;}
  friend bool operator != (const mint &a,const mint &b){return a.v!=b.v;}
  
  type &data(){return v;}
  const type &data()const{return v;}
  
  mint &operator += (const mint &b){v=v>=mod-b.v?v-(mod-b.v):v+b.v;return *this;}
  mint &operator -= (const mint &b){v=v<b.v?v+(mod-b.v):v-b.v;return *this;}
  mint &operator *= (const mint &b){v=type2(v)*b.v%mod;return *this;}
  mint operator + ()const{return *this;}
  mint operator - ()const{return mint()-=*this;}
  mint &operator ++ (){v=v+1==mod?0:v+1;return *this;}
  mint &operator -- (){v=v?v-1:mod-1;return *this;}
  mint operator ++ (int){mint res=*this;v=v+1==mod?0:v+1;return res;}
  mint operator -- (int){mint res=*this;v=v?v-1:mod-1;return res;}
  friend mint operator + (const mint &a,const mint &b){return mint(a)+=b;}
  friend mint operator - (const mint &a,const mint &b){return mint(a)-=b;}
  friend mint operator * (const mint &a,const mint &b){return mint(a)*=b;}
  
  template<class input_type>
  mint pow(input_type k)const{
    mint a=*this,res=1;
    for (;k;k>>=1,a*=a)
      if (k&1) res*=a;
    return res;
  }
  
  mint inv()const{return pow(mod-2);}
  
  mint &operator /= (const mint &b){return *this*=b.inv();}
  friend mint operator / (const mint &a,const mint &b){return mint(a)/=b;}
  
};

typedef modint<int,int64,998244353> mint;

const int N=2000000;
const mint inv2=mint(2).inv();

int test_o;
uint64 seed;

uint64 Rand(uint64 &x){
  x^=(x<<13);
  x^=(x>>7);
  x^=(x<<17);
  return x;
}

int n,cq,x;
int64 k_max;
mint a_st[N+9];

void In(){
  scanf("%d%d%d%lld",&n,&cq,&x,&k_max);
  for (int i=1;i<=n;++i)
    scanf("%d",&a_st[i].data());
}

namespace Sub0{

vector<mint> a[N+9];

void Get_a(){
  a[0].resize(n+1);
  for (int i=1;i<=n;++i) a[0][i]=a_st[i];
  for (int i=1;i<=k_max;++i){
    a[i].resize(n+1);
    for (int j=1;j<=n>>1;++j) a[i][j]=a[i-1][j]+a[i-1][n-j+1];
    for (int j=n;j>=1;--j) a[i][j]=a[i][j+1>>1]*inv2;
  }
}

void Out(){
  int64 ans=0;
  for (int i=1;i<=cq;++i){
    int64 k=Rand(seed)%k_max;
    ans^=1LL*i*a[k][x].data();
  }
  printf("%lld\n",ans);
}

void work(){
  Get_a();
  Out();
}

}

namespace Sub1{

typedef vector<mint> vec;
typedef vector<vector<mint>> matrix;

int m,nm;

matrix zero(){return matrix(m,vec(m));}

matrix one(){
  matrix res=zero();
  for (int i=0;i<m;++i) res[i][i]=1;
  return res;
}

matrix operator * (const matrix &a,const matrix &b){
  matrix res=zero();
  for (int i=0;i<m;++i)
    for (int j=0;j<m;++j)
      for (int k=0;k<m;++k)
        res[i][k]+=a[i][j]*b[j][k];
  return res;
}

vec operator * (const matrix &a,const vec &b){
  vec res(m);
  for (int i=0;i<m;++i)
    for (int j=0;j<m;++j)
      res[i]+=a[i][j]*b[j];
  return res;
}

const int C=60;

vector<vector<mint>> a;

void Get_a(){
  a.clear();
  a.push_back({});
  a[0].resize(n+1);
  for (int i=1;i<=n;++i) a[0][i]=a_st[i];
  m=n;
  for (int i=1;m&1^1;m>>=1,++i){
    a.push_back({});
    a[i].resize(n+1);
    for (int j=1;j<=n>>1;++j) a[i][j]=a[i-1][j]+a[i-1][n-j+1];
    for (int j=n;j>=1;--j) a[i][j]=a[i][j+1>>1]*inv2;
  }
  nm=n/m;
}

vec f;
matrix tr;

void Get_tr(){
  f.resize(m);
  for (int i=0,j=1;i<m;++i,j+=nm) f[i]=a.back()[j];
  tr=zero();
  for (int i=0;i<m;++i)
    if (i<m>>1){
      tr[i<<1][i]=inv2;
      tr[i<<1|1][i]=inv2;
    }else if (i==m>>1){
      tr[m-1][i]=1;
    }else{
      tr[m-1-i<<1][i]=inv2;
      tr[m-1-i<<1|1][i]=inv2;
    }
}

matrix pw[C+9];

void Get_pw(){
  pw[0]=tr;
  for (int i=1;i<C;++i) pw[i]=pw[i-1]*pw[i-1];
}

vec Query(int64 k){
  vec res=f;
  for (int i=C-1;i>=0;--i)
    if (k>>i&1) res=pw[i]*res;
  return res;
}

void Out(){
  int64 ans=0;
  for (int i=1;i<=cq;++i){
    int64 k=Rand(seed)%k_max;
    if (k<a.size()){
      ans^=1LL*i*a[k][x].data();
    }else{
      ans^=1LL*i*Query(k-a.size()+1)[(x-1)/nm].data();
    }
  }
  printf("%lld\n",ans);
}

void work(){
  Get_a();
  Get_tr();
  Get_pw();
  Out();
}

}

void work(){
  In();
  if (test_o<=2) Sub0::work();
  else Sub1::work();
}

int main(){
  freopen("noodle.in","r",stdin);
  freopen("noodle.out","w",stdout);
  int T=1;
  scanf("%d%d%llu",&test_o,&T,&seed);
  for (;T--;) work();
  return 0;
}
