#include <bits/stdc++.h>
using namespace std;
const int N = 100005,P = 998244353,I2 = (P + 1) / 2;
using ll = long long;
using ull = unsigned long long;
using I128 = __int128_t;
int test,T;ull seed;ll mxk;
ll qpow(ll a,ll b)
{
    if (b >= P - 1) b %= P - 1;
    ll ret = 1;
    while (b)
    {
        if (b & 1) ret = ret * a % P;
        a = a * a % P;b >>= 1;
    }
    return ret;
}
ll qpow(ll a,ll b,ll P)
{
    ll ret = 1;
    while (b)
    {
        if (b & 1) ret = I128(ret) * a % P;
        a = I128(a) * a % P;b >>= 1;
    }
    return ret;
}
ull rd(ull &x) { x ^= (x << 13);x ^= (x >> 7);x ^= (x << 17);return x; }
ll a[N];int n,q,x;
namespace Subtask8
{
    const int N = 5015;
    ll coef[N][N],ans[N],sum[N],tans[N];
    ll solve()
    {
        // cerr << "TT" << endl;
        fill(coef[0] + 1,coef[0] + n + 1,0);
        coef[0][x] = 1;map<vector<ll>,int> lst;
        int diff = 0,_cnt = 0,st = 0,lim = 0;ll _ret = 0;
        for (int i = 0;i <= n + 5;i++)
        {
            // cerr << "I=" << i << ' ' << diff << endl;
            auto &a = coef[i],&b = coef[i + 1];lim = i;
            fill(b + 1,b + n + 1,0);
            for (int j = 1;j <= n;j++) b[(j + 1) / 2] += a[j] * I2 % P,b[n - (j + 1) / 2 + 1] += a[j] * I2 % P;
            for (int j = 1;j <= n;j++) b[j] %= P;
            vector<ll> cur(n);for (int j = 1;j <= n;j++) cur[j - 1] = a[j] * qpow(2,i) % P;
            for (int j = 1;j < n;j++) cur[j] -= cur[0];
            cur[0] = 0;
            auto &ref = lst[cur];
            if (ref)
            {
                if (diff != i - ref) diff = i - ref,st = i,_cnt = 1;
                else {if (++_cnt >= 3) break;}
            }
            ref = i;
        }
        for (int i = 0;i <= lim;i++)
        {
            ans[i] = 0;for (int j = 1;j <= n;j++) ans[i] += coef[i][j] * a[j] % P;
            ans[i] %= P;
            if (i >= st)
            {
                for (int j = 1;j <= n;j++) coef[i][j] = coef[i][j] * qpow(2,i) % P;
                for (int j = 2;j <= n;j++) coef[i][j] -= coef[i][1];
                coef[i][1] = 0;sum[i] = accumulate(coef[i] + 1,coef[i] + n + 1,0);
                tans[i] = 0;for (int j = 1;j <= n;j++) tans[i] = (tans[i] + (P + coef[i][j]) % P * a[j]) % P;
            }
        }
        // cerr << "II" << endl;
        a[0] = accumulate(a + 1,a + n + 1,0ll) % P;
        ll mod = n * 1ll * P;
        for (int tc = 1;tc <= q;tc++)
        {
            // ll kk;cin >> kk;
            ll kk = rd(seed) % mxk;
            if (kk <= lim) {_ret ^= tc * ans[kk];/*cerr << "A" << ans[kk] << endl;*/continue;}
            int p = (kk - st) % diff + st;ll curans = tans[p];
            // cerr << "Query" << kk << ' ' << qpow(2,kk) << ' ' << coef[p][0] << ' ' << p << ' ' << tans[p] << endl;
            ll all = (qpow(2,kk,mod) - coef[p][0] % mod + mod) % mod / n;
            assert((all * n + coef[p][0]) % P == qpow(2,kk));curans += all * a[0] % P;
            curans = curans % P * qpow(qpow(2,kk),P - 2) % P;_ret ^= curans * tc;
            // cerr << "XX" << curans << endl;
        }
        return _ret;
    }
}
namespace Subtask6
{
    const int N = 2000015;
    ll coef[25][N],ans[N],sum[N],tans[N];
    ll solve()
    {
        fill(coef[0] + 1,coef[0] + n + 1,0);
        coef[0][x] = 1;map<vector<ll>,int> lst;
        int diff = 0,_cnt = 0,st = 0,lim = 0;ll _ret = 0;
        int __range_lim = min(n + 5ll,mxk);
        for (int i = 0;i <= __range_lim;i++)
        {
            auto &a = coef[i],&b = coef[i + 1];lim = i;
            fill(b + 1,b + n + 1,0);
            for (int j = 1;j <= n;j++) b[(j + 1) / 2] += a[j] * I2 % P,b[n - (j + 1) / 2 + 1] += a[j] * I2 % P;
            for (int j = 1;j <= n;j++) b[j] %= P;
            vector<ll> cur(n);for (int j = 1;j <= n;j++) cur[j - 1] = a[j] * qpow(2,i) % P;
            for (int j = 1;j < n;j++) cur[j] -= cur[0];
            cur[0] = 0;
            auto &ref = lst[cur];
            if (ref)
            {
                if (diff != i - ref) diff = i - ref,st = i,_cnt = 1;
                else {if (++_cnt >= 3) break;}
            }
            ref = i;
        }
        for (int i = 0;i <= lim;i++)
        {
            ans[i] = 0;for (int j = 1;j <= n;j++) ans[i] += coef[i][j] * a[j] % P;
            ans[i] %= P;
            if (i >= st)
            {
                for (int j = 1;j <= n;j++) coef[i][j] = coef[i][j] * qpow(2,i) % P;
                for (int j = 2;j <= n;j++) coef[i][j] -= coef[i][1];
                coef[i][1] = 0;sum[i] = accumulate(coef[i] + 1,coef[i] + n + 1,0);
                tans[i] = 0;for (int j = 1;j <= n;j++) tans[i] = (tans[i] + (P + coef[i][j]) % P * a[j]) % P;
            }
        }
        a[0] = accumulate(a + 1,a + n + 1,0ll) % P;
        ll mod = n * 1ll * P;
        for (int tc = 1;tc <= q;tc++)
        {
            ll kk = rd(seed) % mxk;
            if (kk <= lim) {_ret ^= tc * ans[kk];continue;}
            int p = (kk - st) % diff + st;ll curans = tans[p];
            ll all = (qpow(2,kk,mod) - coef[p][0] % mod + mod) % mod / n;
            assert((all * n + coef[p][0]) % P == qpow(2,kk));curans += all * a[0] % P;
            curans = curans % P * qpow(qpow(2,kk),P - 2) % P;_ret ^= curans * tc;
        }
        return _ret;
    }
}
int main ()
{
    freopen("noodle.in","r",stdin);
    freopen("noodle.out","w",stdout);
    ios::sync_with_stdio(false);
    cin >> test >> T >> seed;
    while (T--)
    {
        cin >> n >> q >> x >> mxk;for (int i = 1;i <= n;i++) cin >> a[i];
        if (test <= 11 && n <= 50000) {cout << Subtask8::solve() << '\n';continue;}
        cout << Subtask6::solve() << '\n';
    }
    return 0;
}