시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 223 98 67 44.079%

문제

지난 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
W3sicHJvYmxlbV9pZCI6IjM2ODQiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM1YjRcdWI4MjRcdWM2YjQgXHViYjM4XHVjODFjIiwiZGVzY3JpcHRpb24iOiI8cD5cdWM5YzBcdWIwOWMgYWNtaWNwYy5uZXQgXHViMzAwXHVkNjhjXHVjNWQwXHViMjk0IFx1YjllNFx1YzZiMCBcdWM1YjRcdWI4MjRcdWM2Y2NcdWMxMWMgXHVjNTQ0XHViYjM0XHViM2M0IFx1ZDQ3YyBcdWMwYWNcdWI3OGNcdWM3NzQgXHVjNWM2XHViMjk0IFx1YmIzOFx1YzgxY1x1YWMwMCBcdWIwOThcdWM2NTRcdWM1YzhcdWIyZTQuIFx1YWRmOCBcdWJiMzhcdWM4MWNcdWM3NTggXHViMzcwXHVjNzc0XHVkMTMwXHViOTdjIFx1YjljY1x1YjRkY1x1YjI5MFx1Yjc3YyBcdWM1YzRcdWNjYWRcdWIwOThcdWFjOGMgXHVhY2UwXHVjMGRkXHVkNTVjIFx1YmMzMVx1YzkwMFx1Yzc3NFx1YjI5NCBcdWQ0N2MgXHVjMGFjXHViNzhjXHVjNzc0IFx1YzVjNlx1YjI5NCBcdWFjODNcdWM3NDQgXHViY2Y0XHVhY2UwIFx1ZDA3MCBcdWM4OGNcdWM4MDhcdWM1ZDAgXHViZTYwXHVjODRjXHViMmU0LiBcdWJjMzFcdWM5MDBcdWM3NzRcdWIyOTQgXHViMmU0XHVjNzRjIFx1YjMwMFx1ZDY4Y1x1YzVkMFx1YjI5NCBcdWM1NDRcdWJiMzRcdWIzYzQgXHVkNDgwIFx1YzIxOCBcdWM1YzZcdWIyOTQgXHViYjM4XHVjODFjXHViOTdjIFx1YjBiNFx1YjgyNFx1YWNlMCBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YmMzMVx1YzkwMFx1Yzc3NFx1YWMwMCBcdWI5Y2NcdWI0ZTAgXHViYjM4XHVjODFjXHViMjk0IFx1YjllNFx1YzZiMCBcdWM1YjRcdWI4MjRcdWM2YjQgXHViYjM4XHVjODFjXHVjNzc0XHVhZTMwIFx1YjU0Y1x1YmIzOFx1YzVkMCBcdWM1NDRcdWJiMzRcdWIzYzQgXHVkNDgwIFx1YzIxOCBcdWM1YzZcdWIyZTQuIFx1YjUzMFx1Yjc3Y1x1YzExYywgXHViMzcwXHVjNzc0XHVkMTMwXHViOTdjIFx1Yjc5Y1x1YjM2NFx1YzczY1x1Yjg1YyBcdWI5Y2NcdWI0ZTRcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LiBcdWJiMzhcdWM4MWNcdWIyOTQgXHVjODE1XHVjMjE4IFx1ZDU1OFx1YjA5OFx1Yjk3YyBcdWM3ODVcdWI4MjVcdWJjMWJcdWFjZTAsIFx1YzgxNVx1YzIxOCBcdWQ1NThcdWIwOThcdWI5N2MgXHVjZDljXHViODI1XHVkNTU4XHViMjk0IFx1YmIzOFx1YzgxY1x1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViYzMxXHVjOTAwXHVjNzc0XHViMjk0IFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWI5N2MgVFx1YWMxYyBcdWFjMDBcdWM5YzBcdWIyOTQgXHVjNzg1XHVjZDljXHViODI1XHVjNzQ0IFx1YjljY1x1YjRlNCBcdWFjODNcdWM3NzRcdWIyZTQuIFx1YjUzMFx1Yjc3Y1x1YzExYywgMFx1YmNmNFx1YjJlNCBcdWQwNmNcdWFjNzBcdWIwOTggXHVhYzE5XHVhY2UwIDEwLDAwMFx1YmNmNFx1YjJlNCBcdWM3OTFcdWFjNzBcdWIwOTggXHVhYzE5XHVjNzQwIFx1YzgxNVx1YzIxOCAyVFx1YWMxYyB4PHN1Yj4xPFwvc3ViPiwgLi4uLCB4PHN1Yj4yVDxcL3N1Yj5cdWI5N2MgXHViOWNjXHViNGU0XHVjNWI0XHVjNTdjIFx1ZDU1Y1x1YjJlNC4gXHVhZGY4IFx1YjJlNFx1Yzc0YywgeDxzdWI+MTxcL3N1Yj4sIHg8c3ViPjM8XC9zdWI+LCAuLi4sIHg8c3ViPjJULTE8XC9zdWI+XHVjNzQwIFx1Yzc4NVx1YjgyNSBcdWIzNzBcdWM3NzRcdWQxMzBcdWI4NWMsIHg8c3ViPjI8XC9zdWI+LCB4PHN1Yj40PFwvc3ViPiwgLi4uLCB4PHN1Yj4yVDxcL3N1Yj5cdWIyOTQgXHVjZDljXHViODI1IFx1YjM3MFx1Yzc3NFx1ZDEzMFx1Yjg1YyZuYnNwO1x1YzBhY1x1YzZhOVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViNzljXHViMzY0IFx1YzgxNVx1YzIxOFx1Yjk3YyBcdWI5Y2NcdWI0ZGNcdWIyOTQgXHViYzI5XHViYzk1XHVjNzQwIFx1YWMwNFx1YjJlOFx1ZDU1OFx1YjJlNC4gXHViYTNjXHVjODAwLCAwXHViY2Y0XHViMmU0IFx1ZDA2Y1x1YWM3MFx1YjA5OCBcdWFjMTlcdWFjZTAsIDEwLDAwMFx1YmNmNFx1YjJlNCBcdWM3OTFcdWFjNzBcdWIwOTggXHVhYzE5XHVjNzQwIFx1YzEzOCBcdWM4MTVcdWMyMTggeDxzdWI+MTxcL3N1Yj4sIGEsIGJcdWI5N2MgXHVjNzg0XHVjNzU4XHViODVjIFx1YWNlMFx1Yjk3OFx1YjJlNC4gXHViMDk4XHViYTM4XHVjOWMwIHg8c3ViPmk8XC9zdWI+XHViMjk0IGlcdWI5N2MgMlx1YmQ4MFx1ZDEzMCAyVFx1YWU0Y1x1YzljMCBcdWM5OWRcdWFjMDBcdWMyZGNcdWQwYTRcdWJhNzRcdWMxMWMgXHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1Yzc0MCBcdWMyZGRcdWM3NDQgXHVjNzc0XHVjNmE5XHVkNTc0XHVjMTFjIFx1YjljY1x1YjRlMFx1YjJlNC48XC9wPlxyXG5cclxuPHA+eDxzdWI+aTxcL3N1Yj4gPSAoYSZtaWRkb3Q7eDxzdWI+aS0xPFwvc3ViPiArIGIpIG1vZCAxMDAwMS48XC9wPlxyXG5cclxuPHA+XHViYzMxXHVjOTAwXHVjNzc0XHVhYzAwIFx1YjljY1x1YjRlMCBcdWIzNzBcdWM3NzRcdWQxMzBcdWM3NTggXHVjNzg1XHViODI1XHVjNzc0IFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1Y2Q5Y1x1YjgyNVx1Yzc0NCBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgVFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFRcdWIyOTQgMTAwXHViY2Y0XHViMmU0IFx1Yzc5MVx1YWM3MFx1YjA5OCBcdWFjMTlcdWM3NDAgXHVjNzkwXHVjNWYwXHVjMjE4XHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWI0NThcdWM5ZjggXHVjOTA0XHViZDgwXHVkMTMwIFRcdWFjMWMgXHVjOTA0XHVjNzU4IGlcdWJjODhcdWM5ZjggXHVjOTA0XHVjNWQwXHViMjk0IHg8c3ViPjJpLTE8XC9zdWI+XHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViYWE4XHViNGUwIFx1Yzc4NVx1YjgyNSBcdWIzNzBcdWM3NzRcdWQxMzBcdWIyOTQgXHViYjM4XHVjODFjXHVjNzU4IFx1YWNmY1x1YzgxNVx1Yzc0NCBcdWQxYjVcdWQ1NzQgXHViOWNjXHViNGUwIFx1YjM3MFx1Yzc3NFx1ZDEzMFx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNkMWQgVFx1YWMxYyBcdWM5MDRcdWM1ZDAgXHVjODE1XHViMmY1XHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gaVx1YmM4OFx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgeDxzdWI+Mmk8XC9zdWI+XHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHVjODE1XHViMmY1XHVjNzc0IFx1YzVlY1x1YjdlYyBcdWFjMDBcdWM5YzBcdWM3NzggXHVhY2JkXHVjNmIwXHVjNWQwXHViMjk0IFx1YzU0NFx1YmIzNFx1YWM3MFx1YjA5OCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiIzNjg0IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiRGlzZ3J1bnRsZWQgSnVkZ2UiLCJkZXNjcmlwdGlvbiI6IjxwPk9uY2UgdXBvbiBhIHRpbWUsIHRoZXJlIHdhcyBhbiBOV0VSQyBqdWRnZSB3aXRoIGEgdGVuZGVuY3kgdG8gY3JlYXRlIHNsaWdodGx5IHRvbyBoYXJkIHByb2JsZW1zLiBBcyBhIHJlc3VsdCwgaGlzIHByb2JsZW1zIHdlcmUgbmV2ZXIgc29sdmVkLiBBcyB5b3UgY2FuIGltYWdlLCB0aGlzIG1hZGUgb3VyIGp1ZGdlIHNvbWV3aGF0IGZydXN0cmF0ZWQuIFRoaXMgeWVhciwgdGhpcyBmcnVzdHJhdGlvbiBoYXMgY3VsbWluYXRlZCwgYW5kIGhlIGhhcyBkZWNpZGVkIHRoYXQgcmF0aGVyIHRoYW4gc3BlbmRpbmcgYSBsb3Qgb2YgdGltZSBjb25zdHJ1Y3RpbmcgYSB3ZWxsLWNyYWZ0ZWQgcHJvYmxlbSwgaGUgd2lsbCBzaW1wbHkgd3JpdGUgc29tZSBpbnNhbmVseSBoYXJkIHByb2JsZW0gc3RhdGVtZW50IGFuZCBqdXN0IGdlbmVyYXRlIHNvbWUgcmFuZG9tIGlucHV0IGFuZCBvdXRwdXQgZmlsZXMuIEFmdGVyIGFsbCwgd2h5IGJvdGhlciBoYXZpbmcgcHJvcGVyIHRlc3QgZGF0YSBpZiBub2JvZHkgaXMgZ29pbmcgdG8gdHJ5IHRoZSBwcm9ibGVtIGFueXdheT88XC9wPlxyXG5cclxuPHA+VGh1cywgdGhlIGp1ZGdlIGdlbmVyYXRlcyBhIHRlc3RjYXNlIGJ5IHNpbXBseSBsZXR0aW5nIHRoZSBpbnB1dCBiZSBhIHJhbmRvbSBudW1iZXIsIGFuZCBsZXR0aW5nIHRoZSBvdXRwdXQgYmUgYW5vdGhlciByYW5kb20gbnVtYmVyLiBGb3JtYWxseSwgdG8gZ2VuZXJhdGUgdGhlIGRhdGEgc2V0IHdpdGggVCB0ZXN0IGNhc2VzLCB0aGUganVkZ2UgZ2VuZXJhdGVzIDJUIHJhbmRvbSBudW1iZXJzIHg8c3ViPjE8XC9zdWI+LCAuIC4gLiAsIHg8c3ViPjJUPFwvc3ViPiBiZXR3ZWVuIDAgYW5kIDEwIDAwMCwgYW5kIHRoZW4gd3JpdGVzIFQsIGZvbGxvd2VkIGJ5IHRoZSBzZXF1ZW5jZSB4PHN1Yj4xPFwvc3ViPiwgeDxzdWI+MzxcL3N1Yj4sIHg8c3ViPjU8XC9zdWI+LCAuIC4gLiAsIHg8c3ViPjJUJm1pbnVzOzE8XC9zdWI+IHRvIHRoZSBpbnB1dCBcdWZiMDFsZSwgYW5kIHRoZSBzZXF1ZW5jZSB4PHN1Yj4yPFwvc3ViPiwgeDxzdWI+NDxcL3N1Yj4sIHg8c3ViPjY8XC9zdWI+LCAuIC4gLiAsIHg8c3ViPjJUPFwvc3ViPiB0byB0aGUgb3V0cHV0IFx1ZmIwMWxlLiBUaGUgcmFuZG9tIG51bWJlciBnZW5lcmF0b3IgdGhlIGp1ZGdlIHVzZXMgaXMgcXVpdGUgc2ltcGxlLiBIZSBwaWNrcyB0aHJlZSBudW1iZXJzIHg8c3ViPjE8XC9zdWI+LCBhLCBhbmQgYiBiZXR3ZWVuIDAgYW5kIDEwIDAwMCAoaW5jbHVzaXZlKSwgYW5kIHRoZW4gZm9yIGkgZnJvbSAyIHRvIDJUIGxldHM8XC9wPlxyXG5cclxuPHA+eDxzdWI+aTxcL3N1Yj4gPSAoYSZtaWRkb3Q7eDxzdWI+aS0xPFwvc3ViPiArIGIpIG1vZCAxMCAwMDEuPFwvcD5cclxuXHJcbjxwPllvdSBtYXkgaGF2ZSB0aG91Z2h0IHRoYXQgc3VjaCBhIHBvb3JseSBkZXNpZ25lZCBwcm9ibGVtIHdvdWxkIG5vdCBiZSB1c2VkIGluIGEgY29udGVzdCBvZiBzdWNoIGhpZ2ggc3RhbmRhcmRzIGFzIE5XRVJDLiBXZWxsLCB5b3Ugd2VyZSB3cm9uZy48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPk9uIHRoZSBcdWZiMDFyc3QgbGluZSBvbmUgcG9zaXRpdmUgbnVtYmVyOiB0aGUgbnVtYmVyIG9mIHRlc3RjYXNlcywgYXQgbW9zdCAxMDAuIEFmdGVyIHRoYXQgcGVyIHRlc3RjYXNlOjxcL3A+XHJcblxyXG48cD5PbmUgbGluZSBjb250YWluaW5nIGFuIGludGVnZXIgbiAoMCAmbGU7IG4gJmxlOyAxMCAwMDApOiBhbiBpbnB1dCB0ZXN0Y2FzZS48XC9wPlxyXG5cclxuPHA+VGhlIGlucHV0IFx1ZmIwMWxlIGlzIGd1YXJhbnRlZWQgdG8gYmUgZ2VuZXJhdGVkIGJ5IHRoZSBwcm9jZXNzIGRlc2NyaWJlZCBhYm92ZS48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5QZXIgdGVzdGNhc2U6PFwvcD5cclxuXHJcbjx1bD5cclxuXHQ8bGk+T25lIGxpbmUgd2l0aCBhbiBpbnRlZ2VyIGdpdmluZyB0aGUgYW5zd2VyIGZvciB0aGUgdGVzdGNhc2UuPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+SWYgdGhlcmUgaXMgbW9yZSB0aGFuIG9uZSBvdXRwdXQgXHVmYjAxbGUgY29uc2lzdGVudCB3aXRoIHRoZSBpbnB1dCBcdWZiMDFsZSwgYW55IG9uZSBvZiB0aGVzZSBpcyBhY2NlcHRhYmxlLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

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