선형 합동 수열의 출력값 복원

어떤 대회 운영자가 선형 합동 생성기(linear congruential generator)로 채점 데이터를 만든다. 먼저 $0$ 이상 $10000$ 이하의 정수 세 개 $x_1$, $a$, $b$를 고른다. 그다음 $i = 2, 3, \dots, 2T$에 대해 다음 점화식으로 나머지 값을 만든다.

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

이렇게 만든 수열에서 홀수 번째 값 $x_1, x_3, \dots, x_{2T-1}$은 입력 데이터로, 짝수 번째 값 $x_2, x_4, \dots, x_{2T}$는 출력 데이터로 쓴다.

입력 데이터, 즉 $x_1, x_3, \dots, x_{2T-1}$이 주어진다. 주어진 모든 값과 모순되지 않는 $(a, b)$가 존재하도록 하는 출력 데이터 $x_2, x_4, \dots, x_{2T}$를 복원하여라. 조건을 만족하는 $(a, b)$가 여러 개일 수 있으므로, 그로부터 만들어지는 출력 수열 $(x_2, x_4, \dots, x_{2T})$이 사전순으로 가장 작은 것을 출력한다.

첫째 줄에 $T$가 주어진다. ($1 \le T \le 100$)

둘째 줄부터 $T$개의 줄에 걸쳐, $i$번째 줄에 $x_{2i-1}$이 주어진다. ($0 \le x_{2i-1} \le 10000$)

모든 입력은 위 과정으로 실제로 만들어진 데이터이므로, 조건을 만족하는 $(a, b)$가 적어도 하나 존재함이 보장된다.

$T$개의 줄을 출력한다. $i$번째 줄에는 $x_{2i}$를 출력한다. 단, 전체 출력 수열 $(x_2, x_4, \dots, x_{2T})$이 입력과 모순되지 않는 모든 수열 중 사전순으로 가장 작은 것이 되도록 해야 한다.