#include <bits/stdc++.h>

namespace Oct {

template <typename Type, Type P, typename MulType>
class ModInt {
   protected:
    Type x;

   public:
    inline ModInt() : x(0) {}
    inline ModInt(Type a) : x(a) {}
    explicit inline operator Type() { return x; }
    friend inline ModInt operator+(ModInt a, ModInt b) { return (a.x += b.x) >= P ? a.x - P : a.x; }
    friend inline ModInt operator-(ModInt a, ModInt b) { return (a.x -= b.x) < 0 ? a.x + P : a.x; }
    friend inline ModInt operator*(ModInt a, ModInt b) { return MulType(a.x) * b.x % P; }
    friend inline ModInt &operator+=(ModInt &a, ModInt b) { return (a.x += b.x) >= P ? a.x -= P, a : a; }
    friend inline ModInt &operator-=(ModInt &a, ModInt b) { return (a.x -= b.x) < 0 ? a.x += P, a : a; }
    friend inline ModInt &operator*=(ModInt &a, ModInt b) { return a.x = MulType(a.x) * b.x % P, a; }
    #define templ template <typename ExpType>
    templ inline ModInt Pow(ExpType Exp) {
        ModInt Base(x), Ret(1);
        while (Exp) {
            if (Exp & 1) Ret *= Base;
            Base *= Base, Exp >>= 1;
        }
        return Ret;
    }
    templ friend inline ModInt Pow(ModInt Base, ExpType Exp) { return Base.Pow(Exp); }
    #undef templ
    inline ModInt Inv() { return Pow(P - 2); }
    friend inline ModInt Inv(ModInt a) { return a.Inv(); }
    friend inline ModInt operator~(ModInt a) { return a.Inv(); }
    friend inline ModInt operator/(ModInt a, ModInt b) { return a * ~b; }
    friend inline ModInt &operator/=(ModInt &a, ModInt b) { return a *= ~b; }
};

} // namespace Oct

using int64 = long long;
using uint64 = unsigned long long;

using MInt = Oct::ModInt<int, 998244353, int64>;

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

MInt F2(MInt x) { return (int(x) & 1 ? int(x) + 998244353 : int(x)) >> 1; }

const MInt F21 = F2(1);

using Vec = std::vector<MInt>;
using Mat = std::vector<Vec>;

inline size_t GetN(Mat a) { return a.size(); }
inline size_t GetM(Mat a) { return a.front().size(); }

inline Mat Mul(Mat a, Mat b) {
    assert(GetM(a) == GetN(b));
    int N = GetN(a), K = GetN(b), M = GetM(b);
    Mat c(N, Vec(M));
    for (int i = 0; i < N; ++i) {
        for (int k = 0; k < K; ++k) {
            for (int j = 0; j < M; ++j) c[i][j] += a[i][k] * b[k][j];
        }
    }
    return c;
}

int main() {
    freopen("noodle.in", "r", stdin);
    freopen("noodle.out", "w", stdout);
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr), std::cout.tie(nullptr);
    int test, T;
    uint64 seed;
    std::cin >> test >> T >> seed;
    while (T--) {
        int n, q, x;
        int64 K;
        std::cin >> n >> q >> x >> K, --x;
        std::vector<MInt> a(n);
        for (int i = 0, x; i < n; ++i) std::cin >> x, a[i] = x;
        if (test <= 2) {
            std::vector<std::vector<MInt> > b(K, std::vector<MInt>(n));
            b[0] = a;
            for (int i = 1; i < K; ++i) {
                MInt *f = &*b[i - 1].begin(), *g = &*b[i].begin();
                for (int j = 0; j < n; ++j) g[j] = F2(f[j >> 1] + f[n - 1 - (j >> 1)]);
            }
            int64 Ans = 0, Te = 0;
            while (++Te, q--) {
                int64 k = rd(seed) % K;
                Ans ^= int(b[k][x]) * Te;
            }
            std::cout << Ans << '\n';
        } else if (test == 3 || n == (1 << __builtin_ctz(n))) {
            int c = __builtin_ctz(n) + 1;
            std::vector<std::vector<MInt> > b(c + 1, std::vector<MInt>(n));
            b[0] = a;
            for (int i = 1; i <= c; ++i) {
                MInt *f = &*b[i - 1].begin(), *g = &*b[i].begin();
                for (int j = 0; j < n; ++j) g[j] = F2(f[j >> 1] + f[n - 1 - (j >> 1)]);
            }
            int64 Ans = 0, Te = 0;
            while (++Te, q--) {
                int64 k = rd(seed) % K;
                Ans ^= int(b[std::min(k, int64(c))][x]) * Te;
            }
            std::cout << Ans << std::endl;
        } else if (test >= 4) {
            int c = __builtin_ctz(n) + 1;
            std::vector<std::vector<MInt> > b(c + 1, std::vector<MInt>(n));
            b[0] = a;
            for (int i = 1; i <= c; ++i) {
                MInt *f = &*b[i - 1].begin(), *g = &*b[i].begin();
                for (int j = 0; j < n; ++j) g[j] = F2(f[j >> 1] + f[n - 1 - (j >> 1)]);
            }
            int m = (n >> c) + 1;
            Mat d(1, Vec(m));
            for (int i = 0; i < m; ++i) d[0][i] = b[c][i << c];
            int kc = 63 - __builtin_clzll(K);
            std::vector<Mat> Ba(kc + 1, Mat(m, Vec(m)));
            for (int i = 0; i + 1 < m; ++i) Ba[0][i / 2][i] = Ba[0][m - (i + 3) / 2][i] = F21;
            Ba[0][(m - 1) / 2][m - 1] = 1;
            for (int i = 1; i <= kc; ++i) Ba[i] = Mul(Ba[i - 1], Ba[i - 1]);
            int64 Ans = 0, Te = 0;
            while (++Te, q--) {
                int64 k = rd(seed) % K;
                if (k <= c) {
                    Ans ^= int(b[k][x]) * Te;
                } else {
                    auto Now = d;
                    k -= c;
                    for (int i = 0; i <= kc; ++i) {
                        if ((k >> i) & 1) Now = Mul(Now, Ba[i]);
                    }
                    Ans ^= int(Now[0][x >> c]) * Te;
                }
            }
            std::cout << Ans << std::endl;
        }
    }
    return 0;
}
