Recovering a Linear Congruential Sequence

A contest organizer builds their judge data with a linear congruential generator. First they choose three integers $x_1$, $a$, and $b$, each between $0$ and $10000$ inclusive. Then, for $i = 2, 3, \dots, 2T$, the remaining values are produced by the recurrence

$$x_i = (a \cdot x_{i-1} + b) \bmod 10001$$

In the resulting sequence, the odd-indexed values $x_1, x_3, \dots, x_{2T-1}$ are used as input data and the even-indexed values $x_2, x_4, \dots, x_{2T}$ are used as output data.

You are given the input data $x_1, x_3, \dots, x_{2T-1}$. Recover output data $x_2, x_4, \dots, x_{2T}$ for which some pair $(a, b)$ is consistent with every given value. Because more than one $(a, b)$ may be consistent, output the sequence $(x_2, x_4, \dots, x_{2T})$ that is lexicographically smallest among all consistent sequences.

The first line contains $T$ ($1 \le T \le 100$).

Each of the next $T$ lines contains $x_{2i-1}$ on its $i$-th line ($0 \le x_{2i-1} \le 10000$).

Every input is data that was actually produced by the process above, so at least one consistent pair $(a, b)$ is guaranteed to exist.

Print $T$ lines. The $i$-th line contains $x_{2i}$. The whole output sequence $(x_2, x_4, \dots, x_{2T})$ must be the lexicographically smallest one among all sequences consistent with the given input.