시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 164 77 50 45.455%

문제

지난 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를 출력한다. 정답이 여러가지인 경우에는 아무거나 출력한다.

예제 입력 1

3
17
822
3014

예제 출력 1

9727
1918
4110

힌트

W3sicHJvYmxlbV9pZCI6IjM2ODQiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM1YjRcdWI4MjRcdWM2YjQgXHViYjM4XHVjODFjIiwiZGVzY3JpcHRpb24iOiI8cD5cdWM5YzBcdWIwOWMgYWNtaWNwYy5uZXQgXHViMzAwXHVkNjhjXHVjNWQwXHViMjk0IFx1YjllNFx1YzZiMCBcdWM1YjRcdWI4MjRcdWM2Y2NcdWMxMWMgXHVjNTQ0XHViYjM0XHViM2M0IFx1ZDQ3YyBcdWMwYWNcdWI3OGNcdWM3NzQgXHVjNWM2XHViMjk0IFx1YmIzOFx1YzgxY1x1YWMwMCBcdWIwOThcdWM2NTRcdWM1YzhcdWIyZTQuIFx1YWRmOCBcdWJiMzhcdWM4MWNcdWM3NTggXHViMzcwXHVjNzc0XHVkMTMwXHViOTdjIFx1YjljY1x1YjRkY1x1YjI5MFx1Yjc3YyBcdWM1YzRcdWNjYWRcdWIwOThcdWFjOGMgXHVhY2UwXHVjMGRkXHVkNTVjIFx1YmMzMVx1YzkwMFx1Yzc3NFx1YjI5NCBcdWQ0N2MgXHVjMGFjXHViNzhjXHVjNzc0IFx1YzVjNlx1YjI5NCBcdWFjODNcdWM3NDQgXHViY2Y0XHVhY2UwIFx1ZDA3MCBcdWM4OGNcdWM4MDhcdWM1ZDAgXHViZTYwXHVjODRjXHViMmU0LiBcdWJjMzFcdWM5MDBcdWM3NzRcdWIyOTQgXHViMmU0XHVjNzRjIFx1YjMwMFx1ZDY4Y1x1YzVkMFx1YjI5NCBcdWM1NDRcdWJiMzRcdWIzYzQgXHVkNDgwIFx1YzIxOCBcdWM1YzZcdWIyOTQgXHViYjM4XHVjODFjXHViOTdjIFx1YjBiNFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YmMzMVx1YzkwMFx1Yzc3NFx1YWMwMCBcdWI5Y2NcdWI0ZTAgXHViYjM4XHVjODFjXHViMjk0IFx1YjllNFx1YzZiMCBcdWM1YjRcdWI4MjRcdWM2YjQgXHViYjM4XHVjODFjXHVjNzc0XHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCBcdWM1NDRcdWJiMzRcdWIzYzQgXHVkNDgwIFx1YzIxOCBcdWM1YzZcdWIyZTQuIFx1YjUzMFx1Yjc3Y1x1YzExYywgXHViMzcwXHVjNzc0XHVkMTMwXHViOTdjIFx1Yjc5Y1x1YjM2NFx1YzczY1x1Yjg1YyBcdWI5Y2NcdWI0ZGNcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWJiMzhcdWM4MWNcdWIyOTQgXHVjODE1XHVjMjE4IFx1ZDU1OFx1YjA5OFx1Yjk3YyBcdWM3ODVcdWI4MjVcdWJjMWJcdWFjZTAsIFx1YzgxNVx1YzIxOCBcdWQ1NThcdWIwOThcdWI5N2MgXHVjZDljXHViODI1XHVkNTU4XHViMjk0IFx1YmIzOFx1YzgxY1x1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViYzMxXHVjOTAwXHVjNzc0XHViMjk0IFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWI5N2MgVFx1YWMxYyBcdWFjMDBcdWM5YzBcdWIyOTQgXHVjNzg1XHVjZDljXHViODI1XHVjNzQ0IFx1YjljY1x1YjRlNCBcdWFjODNcdWM3NzRcdWIyZTQuIFx1YjUzMFx1Yjc3Y1x1YzExYywgMFx1YmNmNFx1YjJlNCBcdWQwNmNcdWFjNzBcdWIwOTggXHVhYzE5XHVhY2UwIDEwLDAwMFx1YmNmNFx1YjJlNCBcdWM3OTFcdWFjNzBcdWIwOTggXHVhYzE5XHVjNzQwIFx1YzgxNVx1YzIxOCAyVFx1YWMxYyB4PHN1Yj4xPFwvc3ViPiwgLi4uLCB4PHN1Yj4yVDxcL3N1Yj5cdWI5N2MgXHViOWNjXHViNGU0XHVjNWI0XHVjNTdjIFx1ZDU1Y1x1YjJlNC4gXHVhZGY4IFx1YjJlNFx1Yzc0YywgeDxzdWI+MTxcL3N1Yj4sIHg8c3ViPjM8XC9zdWI+LCAuLi4sIHg8c3ViPjJULTE8XC9zdWI+XHVjNzQwIFx1Yzc4NVx1YjgyNSBcdWIzNzBcdWM3NzRcdWQxMzBcdWI4NWMsIHg8c3ViPjI8XC9zdWI+LCB4PHN1Yj40PFwvc3ViPiwgLi4uLCB4PHN1Yj4yVDxcL3N1Yj5cdWIyOTQgXHVjZDljXHViODI1IFx1YjM3MFx1Yzc3NFx1ZDEzMFx1Yjk3YyBcdWMwYWNcdWM2YTlcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Yjc5Y1x1YjM2NCBcdWM4MTVcdWMyMThcdWI5N2MgXHViOWNjXHViNGRjXHViMjk0IFx1YmMyOVx1YmM5NVx1Yzc0MCBcdWFjMDRcdWIyZThcdWQ1NThcdWIyZTQuIFx1YmEzY1x1YzgwMCwgMFx1YmNmNFx1YjJlNCBcdWQwNmNcdWFjNzBcdWIwOTggXHVhYzE5XHVhY2UwLCAxMCwwMDBcdWJjZjRcdWIyZTQgXHVjNzkxXHVhYzcwXHViMDk4IFx1YWMxOVx1Yzc0MCBcdWMxMzggXHVjODE1XHVjMjE4IHg8c3ViPjE8XC9zdWI+LCBhLCBiXHViOTdjIFx1Yzc4NFx1Yzc1OFx1Yjg1YyBcdWFjZTBcdWI5NzhcdWIyZTQuIFx1YjA5OFx1YmEzOFx1YzljMCB4PHN1Yj5pPFwvc3ViPlx1YjI5NCBpXHViOTdjIDJcdWJkODBcdWQxMzAgMlRcdWFlNGNcdWM5YzAgXHVjOTlkXHVhYzAwXHVjMmRjXHVkMGE0XHViYTc0XHVjMTFjIFx1YjJlNFx1Yzc0Y1x1YWNmYyBcdWFjMTlcdWM3NDAgXHVjMmRkXHVjNzQ0IFx1Yzc3NFx1YzZhOVx1ZDU3NFx1YzExYyBcdWI5Y2NcdWI0ZTBcdWIyZTQuPFwvcD5cclxuXHJcbjxwPng8c3ViPmk8XC9zdWI+ID0gKGEmbWlkZG90O3g8c3ViPmktMTxcL3N1Yj4gKyBiKSBtb2QgMTAwMDEuPFwvcD5cclxuXHJcbjxwPlx1YmMzMVx1YzkwMFx1Yzc3NFx1YWMwMCBcdWI5Y2NcdWI0ZTAgXHViMzcwXHVjNzc0XHVkMTMwXHVjNzU4IFx1Yzc4NVx1YjgyNVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWNkOWNcdWI4MjVcdWM3NDQgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBUXHViMjk0IDEwMFx1YmNmNFx1YjJlNCBcdWM3OTFcdWFjNzBcdWIwOTggXHVhYzE5XHVjNzQwIFx1Yzc5MFx1YzVmMFx1YzIxOFx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViNDU4XHVjOWY4IFx1YzkwNFx1YmQ4MFx1ZDEzMCBUXHVhYzFjIFx1YzkwNFx1Yzc1OCBpXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCB4PHN1Yj4yaS0xPFwvc3ViPlx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YmFhOFx1YjRlMCBcdWM3ODVcdWI4MjUgXHViMzcwXHVjNzc0XHVkMTMwXHViMjk0IFx1YmIzOFx1YzgxY1x1Yzc1OCBcdWFjZmNcdWM4MTVcdWM3NDQgXHVkMWI1XHVkNTc0IFx1YjljY1x1YjRlMCBcdWIzNzBcdWM3NzRcdWQxMzBcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjZDFkIFRcdWFjMWMgXHVjOTA0XHVjNWQwIFx1YzgxNVx1YjJmNVx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIGlcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IHg8c3ViPjJpPFwvc3ViPlx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1YzgxNVx1YjJmNVx1Yzc3NCBcdWM1ZWNcdWI3ZWNcdWFjMDBcdWM5YzBcdWM3NzggXHVhY2JkXHVjNmIwXHVjNWQwXHViMjk0IFx1YzU0NFx1YmIzNFx1YWM3MFx1YjA5OCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMzY4NCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkRpc2dydW50bGVkIEp1ZGdlIiwiZGVzY3JpcHRpb24iOiI8cD5PbmNlIHVwb24gYSB0aW1lLCB0aGVyZSB3YXMgYW4gTldFUkMganVkZ2Ugd2l0aCBhIHRlbmRlbmN5IHRvIGNyZWF0ZSBzbGlnaHRseSB0b28gaGFyZCBwcm9ibGVtcy4gQXMgYSByZXN1bHQsIGhpcyBwcm9ibGVtcyB3ZXJlIG5ldmVyIHNvbHZlZC4gQXMgeW91IGNhbiBpbWFnZSwgdGhpcyBtYWRlIG91ciBqdWRnZSBzb21ld2hhdCBmcnVzdHJhdGVkLiBUaGlzIHllYXIsIHRoaXMgZnJ1c3RyYXRpb24gaGFzIGN1bG1pbmF0ZWQsIGFuZCBoZSBoYXMgZGVjaWRlZCB0aGF0IHJhdGhlciB0aGFuIHNwZW5kaW5nIGEgbG90IG9mIHRpbWUgY29uc3RydWN0aW5nIGEgd2VsbC1jcmFmdGVkIHByb2JsZW0sIGhlIHdpbGwgc2ltcGx5IHdyaXRlIHNvbWUgaW5zYW5lbHkgaGFyZCBwcm9ibGVtIHN0YXRlbWVudCBhbmQganVzdCBnZW5lcmF0ZSBzb21lIHJhbmRvbSBpbnB1dCBhbmQgb3V0cHV0IGZpbGVzLiBBZnRlciBhbGwsIHdoeSBib3RoZXIgaGF2aW5nIHByb3BlciB0ZXN0IGRhdGEgaWYgbm9ib2R5IGlzIGdvaW5nIHRvIHRyeSB0aGUgcHJvYmxlbSBhbnl3YXk/PFwvcD5cclxuXHJcbjxwPlRodXMsIHRoZSBqdWRnZSBnZW5lcmF0ZXMgYSB0ZXN0Y2FzZSBieSBzaW1wbHkgbGV0dGluZyB0aGUgaW5wdXQgYmUgYSByYW5kb20gbnVtYmVyLCBhbmQgbGV0dGluZyB0aGUgb3V0cHV0IGJlIGFub3RoZXIgcmFuZG9tIG51bWJlci4gRm9ybWFsbHksIHRvIGdlbmVyYXRlIHRoZSBkYXRhIHNldCB3aXRoIFQgdGVzdCBjYXNlcywgdGhlIGp1ZGdlIGdlbmVyYXRlcyAyVCByYW5kb20gbnVtYmVycyB4PHN1Yj4xPFwvc3ViPiwgLiAuIC4gLCB4PHN1Yj4yVDxcL3N1Yj4gYmV0d2VlbiAwIGFuZCAxMCAwMDAsIGFuZCB0aGVuIHdyaXRlcyBULCBmb2xsb3dlZCBieSB0aGUgc2VxdWVuY2UgeDxzdWI+MTxcL3N1Yj4sIHg8c3ViPjM8XC9zdWI+LCB4PHN1Yj41PFwvc3ViPiwgLiAuIC4gLCB4PHN1Yj4yVCZtaW51czsxPFwvc3ViPiB0byB0aGUgaW5wdXQgXHVmYjAxbGUsIGFuZCB0aGUgc2VxdWVuY2UgeDxzdWI+MjxcL3N1Yj4sIHg8c3ViPjQ8XC9zdWI+LCB4PHN1Yj42PFwvc3ViPiwgLiAuIC4gLCB4PHN1Yj4yVDxcL3N1Yj4gdG8gdGhlIG91dHB1dCBcdWZiMDFsZS4gVGhlIHJhbmRvbSBudW1iZXIgZ2VuZXJhdG9yIHRoZSBqdWRnZSB1c2VzIGlzIHF1aXRlIHNpbXBsZS4gSGUgcGlja3MgdGhyZWUgbnVtYmVycyB4PHN1Yj4xPFwvc3ViPiwgYSwgYW5kIGIgYmV0d2VlbiAwIGFuZCAxMCAwMDAgKGluY2x1c2l2ZSksIGFuZCB0aGVuIGZvciBpIGZyb20gMiB0byAyVCBsZXRzPFwvcD5cclxuXHJcbjxwPng8c3ViPmk8XC9zdWI+ID0gKGEmbWlkZG90O3g8c3ViPmktMTxcL3N1Yj4gKyBiKSBtb2QgMTAgMDAxLjxcL3A+XHJcblxyXG48cD5Zb3UgbWF5IGhhdmUgdGhvdWdodCB0aGF0IHN1Y2ggYSBwb29ybHkgZGVzaWduZWQgcHJvYmxlbSB3b3VsZCBub3QgYmUgdXNlZCBpbiBhIGNvbnRlc3Qgb2Ygc3VjaCBoaWdoIHN0YW5kYXJkcyBhcyBOV0VSQy4gV2VsbCwgeW91IHdlcmUgd3JvbmcuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5PbiB0aGUgXHVmYjAxcnN0IGxpbmUgb25lIHBvc2l0aXZlIG51bWJlcjogdGhlIG51bWJlciBvZiB0ZXN0Y2FzZXMsIGF0IG1vc3QgMTAwLiBBZnRlciB0aGF0IHBlciB0ZXN0Y2FzZTo8XC9wPlxyXG5cclxuPHA+T25lIGxpbmUgY29udGFpbmluZyBhbiBpbnRlZ2VyIG4gKDAgJmxlOyBuICZsZTsgMTAgMDAwKTogYW4gaW5wdXQgdGVzdGNhc2UuPFwvcD5cclxuXHJcbjxwPlRoZSBpbnB1dCBcdWZiMDFsZSBpcyBndWFyYW50ZWVkIHRvIGJlIGdlbmVyYXRlZCBieSB0aGUgcHJvY2VzcyBkZXNjcmliZWQgYWJvdmUuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+UGVyIHRlc3RjYXNlOjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPk9uZSBsaW5lIHdpdGggYW4gaW50ZWdlciBnaXZpbmcgdGhlIGFuc3dlciBmb3IgdGhlIHRlc3RjYXNlLjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPklmIHRoZXJlIGlzIG1vcmUgdGhhbiBvbmUgb3V0cHV0IFx1ZmIwMWxlIGNvbnNpc3RlbnQgd2l0aCB0aGUgaW5wdXQgXHVmYjAxbGUsIGFueSBvbmUgb2YgdGhlc2UgaXMgYWNjZXB0YWJsZS48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

ACM-ICPC > Regionals > Europe > Northwestern European Regional Contest > NWERC 2008 D번

  • 문제를 번역한 사람: baekjoon
  • 문제의 오타를 찾은 사람: jh05013