23496번 - Program Optimization 다국어

문제

Consider the following C++ code:

#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() % n;
 last ^= query_mex(a, std::min(i, j), std::max(i, j));
 }
 }
 return last;
}

In the program, query_mex(a, l, r) returns the minimum non-negative integers which does not occur in $a_l, a_{l + 1}, \dots, a_{r}$.

Given the value of $n,ドル $a,ドル $q,ドル $k$ and $s,ドル find the returned value of the function.

입력

The first line contains four integers $n,ドル $q,ドル $k$ and $s$ (1ドル \leq n \leq 2\times 10^5,ドル 1ドル \leq q \leq 10^7,ドル 1ドル \leq k \leq 10^9,ドル 0ドル \leq s \leq 10^9$). The second line contains $n$ distinct integers $a_0, a_1, \dots, a_{n - 1}$ (0ドル \leq a_i < n$).

출력

Output an integer denoting the returned value.

제한

힌트