题意：已知xi=(a*xi-1+b) mod 10001，且告诉你x1,x3………x2*t-1,让你求出其偶数列
分析：枚举a，然后通过x1，x3求出b，再验证是否合适

1.设a, b, c为任意整数。若方程ax+by=c的一组整数解为(x0,y0)，则它的任
意整数解都可以写成(x0+kb’, y0-ka’)，其中a’=a/gcd(a,b)，b’=b/gcd(a,b)，k取任意整数。
2.设a, b, c为任意整数，g=gcd(a,b)，方程ax+by=g的一组解是(x0,y0)，则
当c是g的倍数时ax+by=c的一组解是(x0c/g, y0c/g)；当c不是g的倍数时无整数解。

x2=(a∗x1+b)

x3=(a∗x2+b)

联立2个式子

x3=(a∗(a∗x1+b)

x3=(a∗(a∗x1+b)+b)

所以x3+10001∗k=a∗a∗x1+(a+1)∗b;

x3−a∗a∗x1=(a+1)∗b+10001∗(−k);

x3−a∗a∗x1已知，就转化成ax+by=c/∗扩展欧几里得，在中途再用②判定是否是整数解即可

当然这个题目直接暴力a， b也是可以过的，不过效率很差。 
//
//Created by BLUEBUFF 2016/1/11
//Copyright (c) 2016 BLUEBUFF.All Rights Reserved
//

#pragma comment(linker,"/STACK:102400000,102400000")
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//#include <ext/pb_ds/hash_policy.hpp>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <cmath>
#include <cstdio>
#include <time.h>
#include <cstdlib>
#include <cstring>
#include <complex>
#include <sstream> //isstringstream
#include <iostream>
#include <algorithm>
using namespace std;
//using namespace __gnu_pbds;
typedef long long LL;
typedef unsigned long long uLL;
typedef pair<int, LL> pp;
#define REP1(i, a, b) for(int i = a; i < b; i++)
#define REP2(i, a, b) for(int i = a; i <= b; i++)
#define REP3(i, a, b) for(int i = a; i >= b; i--)
#define CLR(a, b) memset(a, b, sizeof(a))
#define MP(x, y) make_pair(x,y)
template <class T1, class T2>inline void getmax(T1 &a, T2 b) { if (b>a)a = b; }
template <class T1, class T2>inline void getmin(T1 &a, T2 b) { if (b<a)a = b; }
const int maxn = 210;
const int maxm = 1e5+5;
const int maxs = 10;
const int maxp = 1e3 + 10;
const int INF  = 1e9;
const int UNF  = -1e9;
//const int mod = 1e9 + 7;
//const int rev = (mod + 1) >> 1; // FWT
//const double PI = acos(-1);
//head
const int mod = 10001;
void ex_gcd(LL a, LL b, LL &d, LL &x, LL &y){
    if(!b) {d = a; x = 1; y = 0;}
    else{ex_gcd(b, a%b, d, y, x); y-= x*(a/b);}
}
LL x[maxn];
int main()
{
    int T;
    scanf("%d", &T);
    for(int i = 1; i < 2 * T; i += 2) scanf("%lld", &x[i]);
    int a;
    for(a = 0; ; a++){
        LL k, b, d;
        LL t = (x[3] - a * a * x[1]);
        ex_gcd(mod, a + 1, d, k, b);
        if(t % d) continue;
        b = b * t / d;
        bool ok = 1;
        for(int i = 2; i <= 2 * T; i++){
            if(i & 1){
                if(x[i] != (a * x[i - 1] + b) % mod){
                    ok = 0;
                    break;
                }
            }
            else{
                x[i] = (a * x[i - 1] + b) % mod;
            }
        }
        if(ok) break;
    }
    for(int i = 2; i <= 2*T; i += 2){
        printf("%lld\n", x[i]);
    }
    return 0;
}