Solution to G. Glad You Came

#include <iostream>
#include <algorithm>

using uint = unsigned int;
using ull = unsigned long long;

int const lgmax = 20;
int const nmax = 100000;
int rmq[1 + lgmax][1 + nmax];

uint x, y, z;

uint rng() {
  x = x ^ (x << 11);
  x = x ^ (x >> 4);
  x = x ^ (x << 5);
  x = x ^ (x >> 14);
  uint w = x ^ y ^ z;
  x = y;
  y = z;
  z = w;
  return z;
}

int lg(uint number) {
  return 31 - __builtin_clz(number);
}

ull solve() {
  int n, m;
  std::cin >> n >> m >> x >> y >> z;
  for(int h = 0; h < lgmax; h++)
    for(int i = 1; i <= n; i++)
      rmq[h][i] = 0;

  for(int i = 1;i <= m; i++) {
    uint l = rng() % n + 1;
    uint r = rng() % n + 1;
    uint val = (rng() & ((1 << 30) - 1));
    if(r < l)
      std::swap(l, r);
    int h = lg(r - l + 1);

    if(rmq[h][l] < val)
      rmq[h][l] = val;
    if(rmq[h][r - (1 << h) + 1] < val)
      rmq[h][r - (1 << h) + 1] = val;
  }
  for(int h = lgmax - 1; 1 <= h; h--)
    for(int i = 1; i <= n - (1 << h) + 1; i++) {
      if(rmq[h - 1][i] < rmq[h][i])
        rmq[h - 1][i] = rmq[h][i];
      if(rmq[h - 1][i + (1 << (h - 1))] < rmq[h][i])
        rmq[h - 1][i + (1 << (h - 1))] = rmq[h][i];
    }
  ull result = 0;

  for(int i = 1; i <= n; i++)
    result ^= (1LL * i * rmq[0][i]);
  return result;
}

int main() {
  int t;
  std::cin >> t;
  for(int testcase = 1; testcase <= t; testcase++) {
    std::cout << solve() << '\n';
  }
  return 0;
}