Recovering the MT19937 Seed

Ame has discovered that if one knows the seed used to initialize the MT19937 engine, one can predict the outcomes of its pseudorandom number generator and thus obtain a precisely collected pickaxe. Ame has traveled the world and, using her brilliant detective skills, computed the first N outputs produced immediately after the initialization of an altered MT19937 engine (where N is one of the engine’s parameters). She has also attached some of the engine’s parameters (which may differ from the standard values found in literature) in the input.

Your task is to determine the seed used during initialization. The seed is guaranteed to be an integer in the range \(0 \le seed < 2^{32}\). You are given the number \(N\), the altered engine parameters, and the N random numbers generated immediately after initialization.

The altered MT19937 engine works as follows:

// All arithmetic is done modulo \(2^w\).
// The parameters are: w, n, m, r, a, u, d, s, b, t, c, l, f

// Initialization of the state array:
state[0] = seed;
for (int i = 1; i < n; i++) {
    state[i] = (f * (state[i-1] ^ (state[i-1] >> (w-2))) + i) mod 2^w;
}

// Extraction procedure (applied on state[i]):
unsigned int temper(unsigned int x) {
    x = x ^ ((x >> u) & d);
    x = x ^ ((x << s) & b);
    x = x ^ ((x <> l);
    return x;
}

// The engine outputs the value temper(state[i]) for i = 0 ... N-1.

Given the N outputs, recover the initial seed. Note: The tempering function is invertible (its inverse involves reversing the bit‐wise operations using techniques similar to those demonstrated in many standard MT19937 seed recovery problems).

inputFormat

The first line contains an integer N — the number of random numbers provided. The second line contains 13 space‐separated integers representing the parameters of the altered MT19937 engine in the following order: w n m r a u d s b t c l f. The third line contains N space‐separated unsigned 32-bit integers, which are the outputs of the engine (each output is the result of applying the tempering function to the corresponding element in the engine state).

You may assume that \(0 \le seed < 2^{32}\) and that the input values are consistent with some valid seed.

outputFormat

Output a single integer — the seed used to initialize the MT19937 engine.

sample

1
32 624 397 31 2567483615 11 4294967295 7 2636928640 15 3985816832 18 1812433253
0

0