시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 171 80 53 45.299%

문제

지난 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+XHVjZDFkIFRcdWFjMWMgXHVjOTA0XHVjNWQwIFx1YzgxNVx1YjJmNVx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIGlcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IHg8c3ViPjJpPFwvc3ViPlx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1YzgxNVx1YjJmNVx1Yzc3NCBcdWM1ZWNcdWI3ZWMgXHVhYzAwXHVjOWMwXHVjNzc4IFx1YWNiZFx1YzZiMFx1YzVkMFx1YjI5NCBcdWM1NDRcdWJiMzRcdWFjNzBcdWIwOTggXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjM2ODQiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJEaXNncnVudGxlZCBKdWRnZSIsImRlc2NyaXB0aW9uIjoiPHA+T25jZSB1cG9uIGEgdGltZSwgdGhlcmUgd2FzIGFuIE5XRVJDIGp1ZGdlIHdpdGggYSB0ZW5kZW5jeSB0byBjcmVhdGUgc2xpZ2h0bHkgdG9vIGhhcmQgcHJvYmxlbXMuIEFzIGEgcmVzdWx0LCBoaXMgcHJvYmxlbXMgd2VyZSBuZXZlciBzb2x2ZWQuIEFzIHlvdSBjYW4gaW1hZ2UsIHRoaXMgbWFkZSBvdXIganVkZ2Ugc29tZXdoYXQgZnJ1c3RyYXRlZC4gVGhpcyB5ZWFyLCB0aGlzIGZydXN0cmF0aW9uIGhhcyBjdWxtaW5hdGVkLCBhbmQgaGUgaGFzIGRlY2lkZWQgdGhhdCByYXRoZXIgdGhhbiBzcGVuZGluZyBhIGxvdCBvZiB0aW1lIGNvbnN0cnVjdGluZyBhIHdlbGwtY3JhZnRlZCBwcm9ibGVtLCBoZSB3aWxsIHNpbXBseSB3cml0ZSBzb21lIGluc2FuZWx5IGhhcmQgcHJvYmxlbSBzdGF0ZW1lbnQgYW5kIGp1c3QgZ2VuZXJhdGUgc29tZSByYW5kb20gaW5wdXQgYW5kIG91dHB1dCBmaWxlcy4gQWZ0ZXIgYWxsLCB3aHkgYm90aGVyIGhhdmluZyBwcm9wZXIgdGVzdCBkYXRhIGlmIG5vYm9keSBpcyBnb2luZyB0byB0cnkgdGhlIHByb2JsZW0gYW55d2F5PzxcL3A+XHJcblxyXG48cD5UaHVzLCB0aGUganVkZ2UgZ2VuZXJhdGVzIGEgdGVzdGNhc2UgYnkgc2ltcGx5IGxldHRpbmcgdGhlIGlucHV0IGJlIGEgcmFuZG9tIG51bWJlciwgYW5kIGxldHRpbmcgdGhlIG91dHB1dCBiZSBhbm90aGVyIHJhbmRvbSBudW1iZXIuIEZvcm1hbGx5LCB0byBnZW5lcmF0ZSB0aGUgZGF0YSBzZXQgd2l0aCBUIHRlc3QgY2FzZXMsIHRoZSBqdWRnZSBnZW5lcmF0ZXMgMlQgcmFuZG9tIG51bWJlcnMgeDxzdWI+MTxcL3N1Yj4sIC4gLiAuICwgeDxzdWI+MlQ8XC9zdWI+IGJldHdlZW4gMCBhbmQgMTAgMDAwLCBhbmQgdGhlbiB3cml0ZXMgVCwgZm9sbG93ZWQgYnkgdGhlIHNlcXVlbmNlIHg8c3ViPjE8XC9zdWI+LCB4PHN1Yj4zPFwvc3ViPiwgeDxzdWI+NTxcL3N1Yj4sIC4gLiAuICwgeDxzdWI+MlQmbWludXM7MTxcL3N1Yj4gdG8gdGhlIGlucHV0IFx1ZmIwMWxlLCBhbmQgdGhlIHNlcXVlbmNlIHg8c3ViPjI8XC9zdWI+LCB4PHN1Yj40PFwvc3ViPiwgeDxzdWI+NjxcL3N1Yj4sIC4gLiAuICwgeDxzdWI+MlQ8XC9zdWI+IHRvIHRoZSBvdXRwdXQgXHVmYjAxbGUuIFRoZSByYW5kb20gbnVtYmVyIGdlbmVyYXRvciB0aGUganVkZ2UgdXNlcyBpcyBxdWl0ZSBzaW1wbGUuIEhlIHBpY2tzIHRocmVlIG51bWJlcnMgeDxzdWI+MTxcL3N1Yj4sIGEsIGFuZCBiIGJldHdlZW4gMCBhbmQgMTAgMDAwIChpbmNsdXNpdmUpLCBhbmQgdGhlbiBmb3IgaSBmcm9tIDIgdG8gMlQgbGV0czxcL3A+XHJcblxyXG48cD54PHN1Yj5pPFwvc3ViPiA9IChhJm1pZGRvdDt4PHN1Yj5pLTE8XC9zdWI+ICsgYikgbW9kIDEwIDAwMS48XC9wPlxyXG5cclxuPHA+WW91IG1heSBoYXZlIHRob3VnaHQgdGhhdCBzdWNoIGEgcG9vcmx5IGRlc2lnbmVkIHByb2JsZW0gd291bGQgbm90IGJlIHVzZWQgaW4gYSBjb250ZXN0IG9mIHN1Y2ggaGlnaCBzdGFuZGFyZHMgYXMgTldFUkMuIFdlbGwsIHlvdSB3ZXJlIHdyb25nLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+T24gdGhlIFx1ZmIwMXJzdCBsaW5lIG9uZSBwb3NpdGl2ZSBudW1iZXI6IHRoZSBudW1iZXIgb2YgdGVzdGNhc2VzLCBhdCBtb3N0IDEwMC4gQWZ0ZXIgdGhhdCBwZXIgdGVzdGNhc2U6PFwvcD5cclxuXHJcbjxwPk9uZSBsaW5lIGNvbnRhaW5pbmcgYW4gaW50ZWdlciBuICgwICZsZTsgbiAmbGU7IDEwIDAwMCk6IGFuIGlucHV0IHRlc3RjYXNlLjxcL3A+XHJcblxyXG48cD5UaGUgaW5wdXQgXHVmYjAxbGUgaXMgZ3VhcmFudGVlZCB0byBiZSBnZW5lcmF0ZWQgYnkgdGhlIHByb2Nlc3MgZGVzY3JpYmVkIGFib3ZlLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlBlciB0ZXN0Y2FzZTo8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5PbmUgbGluZSB3aXRoIGFuIGludGVnZXIgZ2l2aW5nIHRoZSBhbnN3ZXIgZm9yIHRoZSB0ZXN0Y2FzZS48XC9saT5cclxuPFwvdWw+XHJcblxyXG48cD5JZiB0aGVyZSBpcyBtb3JlIHRoYW4gb25lIG91dHB1dCBcdWZiMDFsZSBjb25zaXN0ZW50IHdpdGggdGhlIGlucHV0IFx1ZmIwMWxlLCBhbnkgb25lIG9mIHRoZXNlIGlzIGFjY2VwdGFibGUuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

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

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