考虑如下 C++ 代码：

#include <algorithm>
#include <random>

int query_mex(const int *a, int l, int r);

int simulate(int n, int *a, int q, int k, int s) {
    std::mt19937 gen;
    gen.seed(s);
    int last = 0;
    while (q--) {
        int op = gen() % k;
        int i = (gen() + last) % n;
        if (!op && i) {
            std::swap(a[i - 1], a[i]);
        } else {
            int j = gen() % k;
            last ^= query_mex(a, std::min(i, j), std::max(i, j));
        }
    }
    return last;
}

在程序中，query_mex(a, l, r) 返回在 $a_l, a_{l+1}, \dots, a_r$ 中未出现的最小非负整数。

给定 $n, a, q, k$ 和 $s$ 的值，求该函数的返回值。

输入格式

第一行包含四个整数 $n, q, k$ 和 $s$ ($1 \le n \le 2 \times 10^5, 1 \le q \le 10^7, 1 \le k \le 10^9, 0 \le s \le 10^9$)。

第二行包含 $n$ 个不同的整数 $a_0, a_1, \dots, a_{n-1}$ ($0 \le a_i < n$)。

输出格式

输出一个整数，表示函数的返回值。

样例

输入 1

3 5 1 0
0 1 2

输出 1

3