Description

Ame knows that as long as she can find the seed used to initialize the MT19937 engine, she can figure out how to obtain a Silk Touch pickaxe. So she traveled around the world, and with her clever detective mind, she worked out the first $N$ random numbers generated right after the MT19937 engine was initialized (note: here $N$ is a parameter in the MT19937 engine). Now she gives you these $N$ random numbers, hoping that you can deduce the seed used to initialize the MT19937 engine ($0\le\text{seed}<2^{32}$). Note that Mivicraft does not use the standard MT19937 engine: some parameters are changed compared with the paper, and Ame has appended them to the input. Please help Ame!

Kind Mivik has prepared a simple and easy-to-understand MT19937 implementation for you. Please check it in the attachment.

Input Format

The first line contains 10 non-negative integers, corresponding to the 10 parameters in MT19937: $N$, $M$, $A$, $U$, $S$, $B$, $T$, $C$, $L$, and $F$.

The next $N$ lines each contain one non-negative integer, representing in order the $N$ random numbers generated right after the MT19937 engine was initialized.

Output Format

Output one non-negative integer in a single line, representing the seed used when initializing the MT19937 engine. The testdata guarantees that there is a solution. If there are multiple solutions, you only need to output any one of them.

见 sample/1.in

见 sample/1.out

见 sample/2.in

见 sample/2.out

Hint

Sample Explanation #1

All 10 parameters use the standard MT19937 parameters, and the seed is 233333. That is, you can generate the same random number sequence with the following program:

#include <iostream>
#include <random>

std::mt19937 engine(233333);
int main() {
	for (int i = 0; i < 624; ++i)
		std::cout << engine() << std::endl;
	return 0;
}

Constraints

This problem uses bundled tests.

For all data, $10\le M<N\le 2\times 10^5$, $0\le A,B,C<2^{32}$, $1\le U,S,T,L\le 31$, $1\le F<2^{32}$, and $F$ is guaranteed to be odd.

The specific limits for each subtask are shown in the table below:

Note: The provided files are encoded in UTF-8. Please use an editor that can recognize this encoding to open them.

Backup link for attachment download: Baidu Netdisk Extraction code: jf9e

Translated by ChatGPT 5