Recovering the Generator Parameters

Long ago, Xiao Ming generated some data with his own random number generator. The generator uses the following two functions:

(\texttt{srand}(\mbox{seed})) – initializes an internal 32‐bit unsigned integer (x) with the value of (\mbox{seed}).

(\texttt{rand}()) – updates (x) by performing these operations in order (all arithmetic is on 32–bit unsigned integers):

[ \begin{array}{lcl} x &\leftarrow& x \oplus (x \ll 13),\[6mm] x &\leftarrow& x \oplus (x \gg 17),\[6mm] x &\leftarrow& x \oplus (x \ll 5),\[4mm] \end{array} ]

and returns (x). After calling (\texttt{srand}(\mbox{seed})), Xiao Ming called (\texttt{rand}()) consecutively (n) times and recorded the remainders when each result was divided by an unknown positive integer (p); that is, he recorded numbers

[ a_i = \texttt{rand}() \bmod p, \quad 1 \le i \le n. ]

Now, although the generator’s implementation (see file generator.cpp) is still available, the parameters (\mbox{seed}) and (p) have been lost. Given the sequence (a_1, a_2, \dots, a_n) (which is guaranteed to be generated by the process described above), your task is to recover any valid pair of parameters (\mbox{seed}) and (p) that could have produced it.

Note: In our test cases we assume that the original generator was used with a modulus (p) so large that no reduction occurred (i.e. the full 32–bit outputs of the xorshift are recorded). Consequently, if (x_i) denotes the value after the (i^{th}) call to (\texttt{rand}()), then we have (a_i = x_i) (and in our recovered answer you may take (p = 2^{32}) or any number larger than any possible (x_i)).

An important observation is that the transformation (f(x) = x \oplus (x \ll 13) \oplus (x \gg 17) \oplus (x \ll 5)) is an invertible operation on 32–bit unsigned integers. In fact, if we denote by

[ \text{rand}(x) = \Bigl(,x \oplus (x \ll 13)\Bigr) \oplus (,\bigl( x \oplus (x \ll 13)\bigr) \gg 17) \oplus \Bigl(,\bigl((x \oplus (x \ll 13)) \oplus ((x \oplus (x \ll 13)) \gg 17)\bigr) \ll 5\Bigr), ]

then one may recover (x) from (y = \text{rand}(x)) by reversing the operations in the reverse order (using bit–by–bit inversions of the XOR–shift operations).

In this problem you are to implement this recovery: given (a_1, a_2, \dots, a_n) (which, under the assumption above, are equal to (f(x)) computed without modulus reduction) you should output the original seed (which is (x_0), recovered from (a_1 = f(x_0))) and a valid modulus (p) (for example, (p = 2^{32})).

inputFormat

The first line contains an integer (n) ((1 \le n \le 10^5)), the number of generated values. The second line contains (n) space–separated integers (a_1, a_2, \dots, a_n) (with (0 \le a_i < p)). It is guaranteed that these values are obtained by consecutively calling (\texttt{rand}()) after a call to (\texttt{srand}(\mbox{seed})) as described.

outputFormat

Output two integers separated by a space: the recovered seed (i.e. the initial value passed to (\texttt{srand})) and a valid modulus (p). If multiple answers exist, output any valid one. (In our case one may output (p = 2^{32}) since the sequence is assumed not to have been reduced modulo a smaller number.)

sample

3
0 0 0

0 2

</p>