Correcting the Mersenne Twister Sequence Value

In this problem, you are given a recursively generated sequence {M_n} defined by the recurrence

\( M_0 \in \mathbb{Z}^+ \cap [0,2^m) \) and for \( n \ge 1 \), \[ M_n = \begin{cases} 2M_{n-1}, &\text{if } 2M_{n-1} < 2^m,\\ (2M_{n-1}-2^m) \;\oplus\; x, &\text{if } 2M_{n-1} \ge 2^m, \end{cases} \]

where \(m \in \mathbb{Z}^+\) is a given positive integer, \(x\) is an integer in \([0,2^m)\) with the property that it is good (i.e. the sequence becomes equidistributed in \([0,2^m)\) when iterated infinitely many times), \(\oplus\) denotes the bitwise XOR operation, and all arithmetic is done with nonnegative integers.

Alice, Bob, and Carol (named Lul, Huahua and Xuanyuan in the original story) are studying pseudo–random number generators. After Lul explained the above method (known as the Mersenne Twister), Huahua used it to compute some values of \(M_k\) for testing randomness. However, during one computation, Huahua mistakenly entered the binary representation of the exponent with extra \(l\) trailing zeros. In other words, instead of inputting the intended binary string representing an integer \(k\), she accidentally appended \(l\) zeros to it. As a result, the computer actually computed the term corresponding to the index

[ k' = k \times 2^l, \quad \text{so that} \quad M_{k'} = M_{k\times 2^l} \text{ was recorded}. ]

Since Huahua lost the original value \(k\) and only kept the erroneous output \(M_{k\times 2^l}\), Carol now asks you to recover the correct value \(M_k\) that should have been computed.

Note: It is guaranteed that the value \(M_{k\times 2^l}\) appears in the sequence starting from the given \(M_0\) at some index that is a multiple of \(2^l\). In other words, there exists a nonnegative integer \(k\) such that if we define the recurrence as above from \(M_0\), then for some index n with \(n = k\times 2^l\) we have \(M_n = M_{k\times 2^l}\>.

Your task is to:

• Find the smallest nonnegative integer \(n\) (possibly zero) such that \(M_n = F\) (the faulty output) and \(n \bmod 2^l = 0\). Let \(k = n/2^l\).
• Then compute \(M_k\) by simulating the recurrence from \(M_0\) for \(k\) steps.

Input Format: The input consists of a single line containing five space‐separated integers:

1. \(m\) (the parameter such that all values lie in \([0,2^m)\));
2. \(x\);
3. \(M_0\);
4. \(l\) (the number of extra trailing zeros that were mistakenly appended to the binary input for the exponent);
5. \(F\) (the faulty computed value, i.e. \(M_{k\times 2^l}\)).

Output Format: Output a single integer, the corrected value \(M_k\).

Explanation:

For example, suppose the input is:

3 3 2 1 3

We have \(m=3, x=3, M_0=2, l=1\). The recurrence is performed modulo \(2^3=8\):

M0 = 2
M1 = f(2) = 2×2 = 4 (since 4 < 8)
M2 = f(4) = (2×4=8, so 8−8=0) XOR 3 = 0 XOR 3 = 3

Here, the faulty value \(F=3\) appears at index \(n=2\), and since \(2 \bmod 2^1 = 0\), we let \(k = 2/2 = 1\). The corrected value is \(M_1 = 4\), so the output should be 4.

It is guaranteed that a solution exists for the given input.

inputFormat

The input consists of one line with five space‐separated integers: m x M0 l F.

• m (1 ≤ m ≤ ?): determines the range [0, 2^m).
• x (0 ≤ x < 2^m), a parameter of the recurrence.
• M0 (0 ≤ M0 < 2^m), the initial value.
• l (nonnegative integer) – the number of extra trailing zeros appended.
• F (0 ≤ F < 2^m), the faulty output value (i.e. the term computed at index k×2^l).

outputFormat

Output a single integer: the correct value Mk computed by simulating the recurrence from M0 for k steps, where k is determined by the condition that the faulty value appears at index n=k×2l.

sample

3 3 2 1 3

4