어려운 문제

지난 acmicpc.net 대회에는 매우 어려워서 아무도 푼 사람이 없는 문제가 나왔었다. 그 문제의 데이터를 만드느라 엄청나게 고생한 백준이는 푼 사람이 없는 것을 보고 큰 좌절에 빠졌다. 백준이는 다음 대회에는 아무도 풀 수 없는 문제를 내려고 한다.

백준이가 만든 문제는 매우 어려운 문제이기 때문에 아무도 풀 수 없다. 따라서, 데이터를 랜덤으로 만들려고 한다. 문제는 정수 하나를 입력받고, 정수 하나를 출력하는 문제이다.

백준이는 테스트 케이스를 T개 가지는 입출력을 만들 것이다. 따라서, 0보다 크거나 같고 10,000보다 작거나 같은 정수 2T개 x1, ..., x2T를 만들어야 한다. 그 다음, x1, x3, ..., x2T-1은 입력 데이터로, x2, x4, ..., x2T는 출력 데이터로 사용한다.

랜덤 정수를 만드는 방법은 간단하다. 먼저, 0보다 크거나 같고, 10,000보다 작거나 같은 세 정수 x1, a, b를 임의로 고른다. 나머지 xi는 i를 2부터 2T까지 증가시키면서 다음과 같은 식을 이용해서 만든다.

xi = (a·xi-1 + b) mod 10001.

백준이가 만든 데이터의 입력이 주어졌을 때, 출력을 구하는 프로그램을 작성하시오.

첫째 줄에 T가 주어진다. T는 100보다 작거나 같은 자연수이다.

둘째 줄부터 T개 줄의 i번째 줄에는 x2i-1이 주어진다.

모든 입력 데이터는 문제의 과정을 통해 만든 데이터이다.

총 T개 줄에 정답을 출력한다. i번째 줄에는 x2i를 출력한다. 정답이 여러 가지인 경우에는 아무거나 출력한다.