/*
 * Warmup Contest #2, September 4, 2010 Problem E 
 * Solution by Jinyu Liu
 * Originally from http://2008.nwerc.eu/contest/problemset (Problem D) 
 * ACM NWERC 2008 Problem D
 * 
 * Brute force over all values of a and b.
 *
 */

#include "stdio.h"
#include <vector>
#include <iostream>
#include <algorithm>
#include <sstream>

using namespace std;

int main() {
	int cases;
	scanf("%d",&cases);
	vector<int> numbers;
	for(int x=0;x<cases;x++) {
			int t;
			scanf("%d",&t);
			numbers.push_back(t);
	}
		int e,f;
		for(int a=0;a<=10000;a++) {
			for(int b=0;b<=10000;b++) {
				int ok=1;
				for(int c=1;c<numbers.size();c++) {
					int x2=(a*numbers[c-1]+b)%10001;
					int x=(a*x2+b)%10001;
					if(!(x==numbers[c])) {
						ok=0; break;
					}
				}
				if(ok) {
					e=a; f=b; b=10001; a=10001;
				}
			}
		}
		for(int y=0;y<numbers.size();y++) {
		//	printf("orig: %d\n",numbers[y]);
			printf("%d\n",(e*numbers[y]+f)%10001);										
		}
}