#ifndef BF
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
inline ull rd(ull &x)
{
    x ^= (x << 13);
    x ^= (x >> 7);
    x ^= (x << 17);
    return x;
}
const int kcz=998244353;
const int maxn=2000005;
const int maxlog=50;
const ll inv2=(kcz+1)>>1;
const int B=16;
#define sum sghfkskdfg
int n,q,x,pos[maxlog],v,x_,n_,l,p2[maxn];
ll a[maxn],sum,b[maxn<<1],temp[maxn<<1],inv2n;
ll s[2][(1<<B)|1];
inline ll qpowinv2(ll k)
{
    k%=kcz-1;
    return s[0][k&((1<<B)-1)]*s[1][k>>B]%kcz;
}
inline ll qpow(ll a,ll k)
{
    ll res=1;
    while(k)
    {
        if(k&1) (res*=a)%=kcz;
        if(k>>=1) (a*=a)%=kcz;
    }
    return /*a*/res;
}
// x, 2n_-1-x
// floor((x+t*2n)/2^k) 0<=t<2^(k-1)
// 2^k*j-x<=tn*2<2^k*(j+1)-x
// a[j]*(ceil((2^k*(j+1)-x)/(2n))-ceil((2^k*j-x)/(2n)))/2^k
// ceil((a+b)/n)-ceil(a/n)=floor(a+n-1+b)-floor(a+n-1)
// =floor(b/n)+floor((a+n-1)%n+b%n)
inline ll calc(int t)
{
    if(temp[t]!=-1) return temp[t];
    ll res=0;
    int i,u;
    for(i=0;i<n_;i++)
        u=(t*(ll)i-x_+(2*n_)-1)%(2*n_),
        (res+=a[i]*((u+t)>=2*n_))%=kcz,
        u=(t*(ll)i+x_)%(2*n_),
        (res+=a[i]*((u+t)>=2*n_))%=kcz;
    return temp[t]=res;
}
inline ll query(ll k)
{
    if(k<=v) { return b[pos[k]+(x>>k)]; }
    if(n_==1) return a[0];
    ll res;
    int t;
    /*x>>=v,*/k-=v,t=p2[(k-1)%l+1];
    // 2*ceil(2^k/(2n))/2^k ceil(2^k/(2n)) X
    // 2*floor(2^k/(2n))/2^k ceil(2^k/(2n))
    res=sum*2%kcz*(inv2n+(/*t?2*n_-t:0*/kcz-t*qpowinv2(k)%kcz*inv2n%kcz))%kcz;
#ifdef DEBUG
    printf("? %lld\n",res);
#endif
    return (res+calc(t)*qpowinv2(k)%kcz)%kcz;
}
int main()
{
    int test,T,i,j;
    ull seed;
    ll k_max,k,ans;
    freopen("noodle.in","r",stdin),freopen("noodle.out","w",stdout);
    scanf("%d%d%llu", &test, &T, &seed);
    for(s[0][0]=1,i=1;i<=(1<<B);i++) s[0][i]=s[0][i-1]*inv2%kcz;
    for(s[1][0]=1,i=1;i<=(1<<B);i++) s[1][i]=s[1][i-1]*s[0][1<<B]%kcz;
    while(T--)
    {
        scanf("%d%d%d%lld", &n, &q, &x, &k_max),x--;
        for(i=0;i<n;i++) scanf("%lld",&a[i]),b[i]=a[i];
        for(v=0;!((n>>v)&1);v++);
        for(pos[0]=0,i=1;i<=v;i++)
        {
            pos[i]=pos[i-1]+(n>>(i-1));
            for(j=0;j<(n>>i);j++)
                b[pos[i]+j]=(b[pos[i-1]+j]+b[pos[i-1]+(n>>(i-1))-1-j])*(ll)inv2%kcz;
        }
        // for(i=0;i<=v;printf("\n"),i++)
        //     for(j=0;j<(n>>i);j++)
        //         printf("%lld ",b[pos[i]+j]);
        x_=x>>v,n_=n>>v;
        for(i=0,sum=0;i<n_;i++) a[i]=b[pos[v]+i],(sum+=a[i])%=kcz;
#ifdef DEBUG
        for(i=0;i<n_;i++) printf("%lld ",a[i]);
        printf("\n%lld\n",sum);
#endif
        for(i=0;i<(n_<<1);i++) temp[i]=-1;
        for(p2[0]=1,p2[1]=2%(2*n_),i=2;i==2 || p2[i-1]!=p2[1];i++)
            p2[i]=p2[i-1]*2%(2*n_);
        l=i-2,inv2n=qpow(2*n_%kcz,kcz-2);
        for(i=1,ans=0;i<=q;i++)
            k=rd(seed)%k_max,
#ifdef DEBUG
            printf("query %lld: %lld\n",k,query(k)),
#endif
            ans^=i*(ll)query(k);
        printf("%lld\n",ans);
    }
    fclose(stdin),fclose(stdout);
    return 0;
}
#else
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
typedef long long ll;
inline ull rd(ull &x)
{
    x ^= (x << 13);
    x ^= (x >> 7);
    x ^= (x << 17);
    return x;
}
const int kcz=998244353;
const int maxn=2000005;
const int maxlog=50;
const int maxk=505;
const ll inv2=(kcz+1)>>1;
int n,q,x,cur;
ll a[2][maxn],ans[maxk];
int main()
{
    int test,T,i;
    ull seed;
    ll k_max,k,res;
    freopen("noodle.in","r",stdin),freopen("noodle.out","w",stdout);
    scanf("%d%d%llu", &test, &T, &seed);
    while(T--)
    {
        scanf("%d%d%d%lld", &n, &q, &x, &k_max),x--;
        for(i=0,cur=0;i<n;i++) scanf("%lld",&a[0][i]);
        for(k=1,ans[0]=a[0][x];k<k_max;ans[k]=a[cur][x],k++)
            for(cur^=1,i=0;i<n;i+=2)
                a[cur][i]=a[cur][i|1]=(a[cur^1][i>>1]+a[cur^1][n-1-(i>>1)])*inv2%kcz;
        for(i=1,res=0;i<=q;i++)
            k=rd(seed)%k_max,
#ifdef DEBUG
            printf("query %lld: %lld\n",k,ans[k]),
#endif
            res^=i*(ll)ans[k];
        printf("%lld\n",res);
    }
    fclose(stdin),fclose(stdout);
    return 0;
}
#endif