시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 (추가 시간 없음) 256 MB222100.000%

## 문제

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.

## 예제 입력 1

3 5 1 0
0 1 2


## 예제 출력 1

3