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 this program, query_mex(a, l, r) returns the smallest non-negative integer that does not occur among $a_l, a_{l + 1}, \dots, a_r$.

Given the values of $n$, $a$, $q$, $k$, and $s$, find the value the function returns.

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, the value the function returns.