Kujou Karen is a girl who loves eating ramen.

One day, she went to eat ramen and discovered that the ramen chef was pulling a noodle of length $n$, where $n$ is guaranteed to be even. Initially, the amount of seasoning at position $i$ is $a_i$.

The following process is called one "ramen pull": 1. Fold the noodle in half. The length of the noodle becomes $n/2$. The amount of seasoning at position $i$ becomes the sum of the seasoning at the original position $i$ and the seasoning at position $n - i + 1$. If the amount of seasoning at position $i$ of the new noodle is $b_i$, then $b_i = a_i + a_{n-i+1}$. 2. Stretch the noodle back to its original length $n$. Each position becomes two positions, and the seasoning amount is divided equally. If the seasoning amount at the current position $i$ is $a'_i$, then $a'_i = \frac{1}{2} \times b_{\lceil i/2 \rceil}$.

Now, for a fixed $x$, you need to answer $q$ queries. For each query, find the amount of seasoning at position $x$ after the noodle has undergone $k$ "ramen pulls". You only need to find the result modulo $998\,244\,353$. Specifically, if the answer is represented as an irreducible fraction $\frac{a}{b}$, output $a \times b^{-1} \pmod{998\,244\,353}$.

Input

Read the data from the file noodle.in.

The first line contains three positive integers test, T, and seed, representing the test case number, the number of data groups, and the generation seed, respectively.

Then $T$ groups of data follow, each consisting of two lines.

The first line of each group contains four positive integers $n, q, x, k_{max}$, representing the length of the noodle, the number of queries, the query position, and the upper bound for $k$ in the generated queries, respectively.

The second line contains $n$ non-negative integers, where the $i$-th integer $a_i$ represents the initial amount of seasoning at position $i$.

To avoid massive input and output, the $q$ queries are generated by a provided generator. Specifically, we provide a C++ code framework noodle_template.cpp for contestants to use (see Appendix). We provide some explanations here:

First, read two 32-bit integer variables test, T, and one unsigned 64-bit integer variable seed from the data. Then loop $T$ times for the $T$ data groups.

In each iteration, calculate for one data group. First, read three 32-bit integer variables $n, q, x$, and one 64-bit integer variable $k_{max}$. Then read $n$ 32-bit integers into the array $a_1, \dots, a_n$.

Next is the part for generating $q$ queries. Each time the rd() function is called, passing seed as a reference parameter, the result of the return value (which is an unsigned 64-bit integer) modulo $k_{max}$ is used as the parameter $k$ for that query. Note that seed will also be modified.

Output

Output to the file noodle.out.

Output $T$ lines, each containing an integer representing the answer for that data group. Specifically, assuming the data group has $q$ queries and the answer to the $i$-th query is $Ans_i$, you need to output $\bigoplus_{i=1}^q (Ans_i \cdot i)$. Note that no modulo is required here. $\oplus$ denotes the bitwise XOR operator.

Constraints

For all test cases: $T \le 10$, $n \le 2 \times 10^6$, $q \le 5 \times 10^7$, $k_{max} \le 10^{18}$, $1 \le x \le n$, $0 \le a_i < 998\,244\,353$, $0 \le seed \le 2^{60} - 1$, and $n$ is guaranteed to be even.

Note: For the sample, the test case number test is 0.

The specific limits for each test case are as follows:

Examples

Input 1

0 2 12345
4 2 1 2
1 4 2 3
6 2 3 3
6 2 5 3 1 4

Output 1

499122196

Note

For Example 1: In the first data group, $\{a_i\}$ is initially $\{1, 4, 2, 3\}$. After one operation, it becomes $\{2, 2, 3, 3\}$. After two operations, it becomes $\{\frac{5}{2}, \frac{5}{2}, \frac{5}{2}, \frac{5}{2}\}$. The generated queries are: Query position: $x = 1$; First query: $k = 0$, $a_x = 1$; Second query: $k = 1$, $a_x = 2$; The answer is $(1 \times 1) \oplus (2 \times 2) = 4 \oplus 1 = 5$.

In the second data group, $\{a_i\}$ is initially $\{6, 2, 5, 3, 1, 4\}$. After one operation, it becomes $\{5, 5, \frac{3}{2}, \frac{3}{2}, 4, 4\}$. After two operations, it becomes $\{\frac{9}{2}, \frac{9}{2}, \frac{9}{2}, \frac{9}{2}, \frac{3}{2}, \frac{3}{2}\}$. The generated queries are: Query position: $x = 3$; First query: $k = 2$, $a_x = \frac{9}{2}$, $\frac{9}{2} \equiv 499122181 \pmod{998244353}$; Second query: $k = 0$, $a_x = 5$; The answer is $(499122181 \times 1) \oplus (5 \times 2) = 499122181 \oplus 10 = 499122191$.

Final answer: $5 \oplus 499122191 = 499122196$.

Implementation Details

#include <bits/stdc++.h>
using namespace std;

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

int main() {
    int test, T;
    unsigned long long seed;
    scanf("%d%d%llu", &test, &T, &seed);
    for (int Case = 1; Case <= T; Case++) {
        int n, q, x;
        long long k_max;
        scanf("%d%d%d%lld", &n, &q, &x, &k_max);
        vector<int> a(n + 1);
        for (int i = 1; i <= n; i++) {
            scanf("%d", &a[i]);
        }
        for (int i = 1; i <= q; i++) {
            long long k = rd(seed) % k_max;
            /*
            Code your solution here.
            */
        }
    }
}