// This Code was made by Chinese_zjc_.
#include <bits/stdc++.h>
const int MOD = 998244353;
struct mint
{
    unsigned v;
    mint(unsigned v_=0):v(v_){}
    mint&operator+=(const mint &X){return (v+=X.v)>=MOD?v-=MOD:v,*this;}
    mint&operator-=(const mint &X){return (v+=MOD-X.v)>=MOD?v-=MOD:v,*this;}
    mint&operator*=(const mint &X){return v=1llu*v*X.v%MOD,*this;}
    mint&operator/=(const mint &X){return *this*=X.inv();}
    mint pow(long long B)const
    {
        B%=MOD-1;
        if(B<0)
            B+=MOD-1;
        mint res=1,A=*this;
        while(B)
        {
            if(B&1)
                res*=A;
            A*=A;
            B>>=1;
        }
        return res;
    }
    mint inv()const{return pow(MOD-2);}
    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;}
    friend mint operator/(const mint &A,const mint &B){return mint(A)/=B;}
    friend std::istream&operator>>(std::istream&A,mint &B){return A>>B.v;}
    friend std::ostream&operator<<(std::ostream&A,const mint &B){return A<<B.v;}
    friend bool operator==(const mint &A,const mint &B){return A.v==B.v;}
};
mint a[2000005],b[2000005],ANS[25],inv2=(MOD+1)/2;
int n,q,x;
unsigned m=1;
struct pair
{
    unsigned a;
    mint b;
    pair(unsigned long long v=0):a(v%m),b(v/m){}
    pair& operator+=(const pair &X){return (a+=X.a)>=m?a-=m,b+=1:a,b+=X.b,*this;}
    pair& operator*=(const pair &X){return b=b*X.b*m+a*X.b+b*X.a+1llu*a*X.a/m,a=1llu*a*X.a%m,*this;}
    friend pair operator+(const pair &A,const pair &B){return pair(A)+=B;}
    friend pair operator*(const pair &A,const pair &B){return pair(A)*=B;}
}pw[3][1000005];
long long k_max;
unsigned long long seed;
unsigned long long rd()
{
    seed ^= (seed << 13);
    seed ^= (seed >> 7);
    seed ^= (seed << 17);
    return seed;
}
void play()
{
    for(int i=0;i!=n;++i)
        b[i]=(a[i]+a[n-i-1])*inv2;
    for(int i=0;i!=n;++i)
        a[i]=b[i>>1];
}
mint get(pair X){return X.b*2+(X.a>x)+(X.a>m-x-1);}
int main()
{
    freopen("noodle.in","r",stdin)&&freopen("noodle.out","w",stdout);
    int test, T;
    std::cin>>test>>T>>seed;
    while(T--)
    {
        std::cin>>n>>q>>x>>k_max;
        --x;
        m=2*n;
        for(int i=0;i!=n;++i)
            std::cin>>a[i];
        if(!(n&(n-1)))
        {
            unsigned long long tot=0;
            for(int i=0;i!=25;++i)
            {
                ANS[i]=a[x];
                play();
            }
            for(int i=1;i<=q;++i)
            {
                long long k=rd()%k_max;
                if(k>=25)
                    k=24;
                tot^=1llu*ANS[k].v*i;
            }
            std::cout<<tot<<std::endl;
            continue;
        }
        pw[0][0]=pw[1][0]=pw[2][0]=1;
        pw[0][1]=2;
        for(int i=2;i<=1000000;++i)
            pw[0][i]=pw[0][i-1]*pw[0][1];
        pw[1][1]=pw[0][1000000];
        for(int i=2;i<=1000000;++i)
            pw[1][i]=pw[1][i-1]*pw[1][1];
        pw[2][1]=pw[1][1000000];
        for(int i=2;i<=1000000;++i)
            pw[2][i]=pw[2][i-1]*pw[2][1];
        // for(int k=0;k!=n;++k)
        // {
        //     std::cout<<"k="<<k<<std::endl;
        //     std::fill(a,a+n,0);
        //     a[k]=1;
        //     std::map<std::vector<int>,int> map;
        //     for(int i=1;i<=1000;++i)
        //     {
        //         play();
        //         std::vector<int> len;
        //         for(mint *j=a,*l=a;j!=a+n;j=l)
        //         {
        //             while(l!=a+n&&*l==*j)
        //                 ++l;
        //             len.push_back(l-j);
        //             std::cout<<*j<<"*"<<l-j<<' ';
        //         }
        //         std::cout<<std::endl;
        //         if(map.count(len))
        //         {
        //             std::cout<<"len="<<i-map[len]<<std::endl;
        //             break;
        //         }
        //         else
        //         {
        //             map[len]=i;
        //         }
        //     }
        // }
        unsigned long long tot=0;
        for(int i=1;i<=q;++i)
        {
            long long k = rd() % k_max;
            // std::cout<<k<<std::endl;
            mint ans=0;
            pair P=pw[0][k%1000000]*pw[1][k/1000000%1000000]*pw[2][k/1000000000000];
            // std::cout<<P.a<<' '<<P.b<<std::endl;
            mint lst=0;
            for(int j=0;j!=n;++j)
            {
                mint cur=get((j+1)*P);
                ans+=(cur-lst)*a[j];
                lst=cur;
            }
            ans*=mint(2).pow(MOD-1-k);
            tot^=1llu*ans.v*i;
        }
        std::cout<<tot<<std::endl;
    }
}