#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>

constexpr int N = 2000005;
constexpr int p = 998244353;
constexpr int inv2 = (p + 1) >> 1;

int add(int x, int y) { return (x += y) >= p ? x - p : x; }
int sub(int x, int y) { return (x -= y) < 0 ? x + p : x; }
int mul(int x, int y) { return static_cast<unsigned long long>(x) * y % p; }
int power(int x, int y) { int ans = 1; for (; y; y >>= 1) { if (y & 1) ans = mul(ans, x); x = mul(x, x); } return ans; }

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

int test, T;
unsigned long long seed;
int a[N], b[N];

struct matrix {
    int r, c;
    std::vector<std::vector<int>> val;
    matrix(): r(0), c(0) {}
    matrix(int r, int c): r(r), c(c) {
        val.resize(r);
        for (int i = 0; i < r; ++i) val[i].resize(c);
    }
    matrix operator *(const matrix& a) {
        matrix ans(r, a.c);
        for (int k = 0; k < c; ++k)
            for (int i = 0; i < r; ++i)
                for (int j = 0; j < a.c; ++j) {
                    ans.val[i][j] = (static_cast<unsigned long long>(val[i][k]) * a.val[k][j] + ans.val[i][j]) % p;
                }
        return ans;
    }
    /*
    matrix operator ^(const matrix& a) {
        matrix ans(r, a.c);
        for (int k = 0; k < c; ++k)
            for (int i = 0; i < r; ++i)
                for (int j = 0; j < a.c; ++j) {
                    ans.val[i][j] += val[i][k] * a.val[k][j];
                }
        int min = 1e9;
        for (int i = 0; i < r; ++i)
            for (int j = 0; j < a.c; ++j)
                min = std::min(min, ans.val[i][j]);
        for (int i = 0; i < r; ++i)
            for (int j = 0; j < a.c; ++j)
                ans.val[i][j] -= min;
        return ans;
    }
    */
};

bool comp(const matrix& a, const matrix& b) {
    if (a.r != b.r) return false;
    if (a.c != b.c) return false;
    for (int i = 0; i < a.r; ++i)
        for (int j = 0; j < a.c; ++j)
            if (a.val[i][j] != b.val[i][j]) return false;
    return true;
}

int main() {
    freopen("noodle.in", "r", stdin);
    freopen("noodle.out", "w", stdout);
    std::ios::sync_with_stdio(false), std::cin.tie(nullptr);
    std::cin >> test >> T >> seed;
    while (T--) {
        int n, q, x;
        long long k_max;
        std::cin >> n >> q >> x >> k_max;
        --x;
        for(int i = 0; i < n; ++i) std::cin >> a[i];
        std::vector<int> prep;
        long long max_test3;
        matrix base;
        std::vector<matrix> prep2;
        int cycle_start, cycle_length;
        bool found = false;
        if (test <= 2) {
            prep.resize(k_max);
            prep[0] = a[x];
            int now = 1;
            for (int i = 1; i < k_max; ++i) {
                for (int j = 0; j < n >> 1; ++j) b[j] = add(a[j], a[n - 1 - j]);
                for (int j = 0, k = 0; j < n; j += 2, ++k) a[j] = a[j + 1] = b[k];
                now = mul(now, inv2);
                prep[i] = mul(a[x], now);
            }
        } else if (test == 3) {
            int max = 31 ^ __builtin_clz(n);
            max_test3 = max;
            ++max;
            prep.resize(max);
            prep[0] = a[x];
            int now = 1;
            for (int i = 1; i < max; ++i) {
                for (int j = 0; j < n >> 1; ++j) b[j] = add(a[j], a[n - 1 - j]);
                for (int j = 0, k = 0; j < n; j += 2, ++k) a[j] = a[j + 1] = b[k];
                now = mul(now, inv2);
                prep[i] = mul(a[x], now);
            }
        } else if (test == 4) {
            base = matrix(n, n);
            for (int i = 0, j = 0; i < n; i += 2, ++j) base.val[i][j] = base.val[i][n - 1 - j] = base.val[i + 1][j] = base.val[i + 1][n - 1 - j] = inv2;
        } else {
            base = matrix(n, n);
            for (int i = 0, j = 0; i < n; i += 2, ++j) base.val[i][j] = base.val[i][n - 1 - j] = base.val[i + 1][j] = base.val[i + 1][n - 1 - j] = 1;
            prep2.push_back(base);
            matrix now(base);
            for (int i = 1; ; ++i) {
                now = now * base;
                matrix tmp(now);
                int min = 1e9;
                for (int j = 0; j < n; ++j)
                    for (int k = 0; k < n; ++k)
                        min = std::min(min, tmp.val[j][k]);
                for (int j = 0; j < n; ++j)
                    for (int k = 0; k < n; ++k)
                        tmp.val[j][k] -= min;
                for (int j = 0; j < i; ++j)
                    if (comp(tmp, prep2[j])) {
                        found = true;
                        cycle_start = j;
                        cycle_length = i - j;
                        break;
                    }
                if (found) break;
                prep2.push_back(tmp);
            }
        }
        int invn = power(n, p - 2);
        unsigned long long res = 0;
        for (int i = 1; i <= q; ++i) {
            long long k = rd(seed) % k_max;
            int ans;
            if (test <= 2) {
                ans = prep[k];
            } else if (test == 3) {
                ans = prep[std::min(k, max_test3)];
            } else if (test == 4) {
                matrix tmp = base;
                matrix res(n, n);
                for (int j = 0; j < n; ++j) res.val[j][j] = 1;
                for (; k; k >>= 1) {
                    if (k & 1) res = res * tmp;
                    tmp = tmp * tmp;
                }
                ans = 0;
                for (int j = 0; j < n; ++j) ans = (static_cast<unsigned long long>(res.val[x][j]) * a[j] + ans) % p;
            } else {
                if (!k) ans = a[x];
                else {
                    --k;
                    std::vector<int> v;
                    if (k < cycle_start) v = prep2[k].val[x];
                    else v = prep2[(k - cycle_start) % cycle_length + cycle_start].val[x];
                    int allsum = power(2, (k + 1) % (p - 1));
                    int allinv = power(allsum, p - 2);
                    for (int i = 0; i < n; ++i) allsum = sub(allsum, v[i]);
                    allsum = mul(allsum, invn);
                    ans = 0;
                    for (int i = 0; i < n; ++i) ans = add(ans, mul(add(allsum, v[i]), a[i]));
                    ans = mul(ans, allinv);
                }
            }
            res ^= static_cast<unsigned long long>(ans) * i;
        }
        std::cout << res << '\n';
    }
    return 0;
}
