시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 62 11 8 57.143%

문제

상근이와 친구들이 술자리에서 하는 게임은 소수 사이클 게임이다. 각 사람은 1번부터 N번으로 나타낸다.

게임을 시작하기에 앞서 동그란 의자 N-1개와 네모난 의자 1개를 준비한다. 의자는 원을 이루어서 배치한다. 먼저, 1번이 네모난 의자에 앉고, 다음 2번부터는 반시계방향으로 차례대로 의자에 앉는다. 모든 사람은 원의 중심을 바라보고 있다.

게임은 총 K개 라운드로 이루어져 있다. i번째 라운드 시작되면 네모에 앉은 사람이 자리에서 일어나서 "내가 네모야!"라고 외친다. 그 다음, 오른쪽에 있는 사람과 자리를 총 Pi번 바꾸게 된다. Pi는 i번째 작은 소수이다.

아래는 N=5, K=3인 예이다.

N, K, A가 주어졌을 때, 게임이 끝난 후에 A의 이웃을 구하는 프로그램을 작성하시오. 

입력

첫째 줄에 N, K, A가 주어진다. (3 ≤ N ≤ 5,000,000, 1 ≤ K ≤ 500,000, 1 ≤ A ≤ N)

출력

게임이 끝난 후에 A의 오른쪽에 있는 사람과 왼쪽에 있는 사람을 출력한다.

예제 입력 1

5 3 1

예제 출력 1

3 5
W3sicHJvYmxlbV9pZCI6IjI4ODIiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMxOGNcdWMyMTggXHVjMGFjXHVjNzc0XHVkMDc0IiwiZGVzY3JpcHRpb24iOiI8cD5cdWMwYzFcdWFkZmNcdWM3NzRcdWM2NDAgXHVjZTVjXHVhZDZjXHViNGU0XHVjNzc0IFx1YzIyMFx1Yzc5MFx1YjlhY1x1YzVkMFx1YzExYyBcdWQ1NThcdWIyOTQgXHVhYzhjXHVjNzg0XHVjNzQwIFx1YzE4Y1x1YzIxOCBcdWMwYWNcdWM3NzRcdWQwNzQgXHVhYzhjXHVjNzg0XHVjNzc0XHViMmU0LiBcdWFjMDEgXHVjMGFjXHViNzhjXHVjNzQwIDFcdWJjODhcdWJkODBcdWQxMzAgTlx1YmM4OFx1YzczY1x1Yjg1YyBcdWIwOThcdWQwYzBcdWIwYjhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWM4Y1x1Yzc4NFx1Yzc0NCBcdWMyZGNcdWM3OTFcdWQ1NThcdWFlMzBcdWM1ZDAgXHVjNTVlXHVjMTFjIFx1YjNkOVx1YWRmOFx1Yjc4MCBcdWM3NThcdWM3OTAgTi0xXHVhYzFjXHVjNjQwIFx1YjEyNFx1YmFhOFx1YjA5YyBcdWM3NThcdWM3OTAgMVx1YWMxY1x1Yjk3YyBcdWM5MDBcdWJlNDRcdWQ1NWNcdWIyZTQuIFx1Yzc1OFx1Yzc5MFx1YjI5NCBcdWM2ZDBcdWM3NDQgXHVjNzc0XHViOGU4XHVjNWI0XHVjMTFjIFx1YmMzMFx1Y2U1OFx1ZDU1Y1x1YjJlNC4gXHViYTNjXHVjODAwLCAxXHViYzg4XHVjNzc0IFx1YjEyNFx1YmFhOFx1YjA5YyBcdWM3NThcdWM3OTBcdWM1ZDAgXHVjNTQ5XHVhY2UwLCBcdWIyZTRcdWM3NGMgMlx1YmM4OFx1YmQ4MFx1ZDEzMFx1YjI5NCBcdWJjMThcdWMyZGNcdWFjYzRcdWJjMjlcdWQ1YTVcdWM3M2NcdWI4NWMgXHVjYzI4XHViODQwXHViMzAwXHViODVjIFx1Yzc1OFx1Yzc5MFx1YzVkMCBcdWM1NDlcdWIyOTRcdWIyZTQuIFx1YmFhOFx1YjRlMCBcdWMwYWNcdWI3OGNcdWM3NDAgXHVjNmQwXHVjNzU4IFx1YzkxMVx1YzJlY1x1Yzc0NCBcdWJjMTRcdWI3N2NcdWJjZjRcdWFjZTAgXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFjOGNcdWM3ODRcdWM3NDAgXHVjZDFkIEtcdWFjMWMgXHViNzdjXHVjNmI0XHViNGRjXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuIGlcdWJjODhcdWM5ZjggXHViNzdjXHVjNmI0XHViNGRjIFx1YzJkY1x1Yzc5MVx1YjQxOFx1YmE3NCBcdWIxMjRcdWJhYThcdWM1ZDAgXHVjNTQ5XHVjNzQwIFx1YzBhY1x1Yjc4Y1x1Yzc3NCBcdWM3OTBcdWI5YWNcdWM1ZDBcdWMxMWMgXHVjNzdjXHVjNWI0XHViMDk4XHVjMTFjICZxdW90O1x1YjBiNFx1YWMwMCBcdWIxMjRcdWJhYThcdWM1N2MhJnF1b3Q7XHViNzdjXHVhY2UwIFx1YzY3OFx1Y2U1Y1x1YjJlNC4gXHVhZGY4IFx1YjJlNFx1Yzc0YywgXHVjNjI0XHViOTc4XHVjYWJkXHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWMwYWNcdWI3OGNcdWFjZmMgXHVjNzkwXHViOWFjXHViOTdjIFx1Y2QxZCBQPHN1Yj5pPFwvc3ViPlx1YmM4OCBcdWJjMTRcdWFmYjhcdWFjOGMgXHViNDFjXHViMmU0LiBQPHN1Yj5pPFwvc3ViPlx1YjI5NCBpXHViYzg4XHVjOWY4IFx1Yzc5MVx1Yzc0MCBcdWMxOGNcdWMyMThcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzU0NFx1Yjc5OFx1YjI5NCBOPTUsIEs9M1x1Yzc3OCBcdWM2MDhcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvcHJpbWVjeWNsZS5wbmdcIiBzdHlsZT1cImhlaWdodDozNTJweDsgd2lkdGg6NjcycHhcIiBcLz48XC9wPlxyXG5cclxuPHA+TiwgSywgQVx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcdWFjOGNcdWM3ODRcdWM3NzQgXHViMDVkXHViMDljIFx1ZDZjNFx1YzVkMCBBXHVjNzU4IFx1Yzc3NFx1YzZjM1x1Yzc0NCBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgTiwgSywgQVx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgzICZsZTsgTiAmbGU7IDUsMDAwLDAwMCwgMSAmbGU7IEsgJmxlOyA1MDAsMDAwLCAxICZsZTsgQSAmbGU7IE4pPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzhjXHVjNzg0XHVjNzc0IFx1YjA1ZFx1YjA5YyBcdWQ2YzRcdWM1ZDAgQVx1Yzc1OCBcdWM2MjRcdWI5NzhcdWNhYmRcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YzBhY1x1Yjc4Y1x1YWNmYyBcdWM2N2NcdWNhYmRcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YzBhY1x1Yjc4Y1x1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMjg4MiIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IktPTE8iLCJkZXNjcmlwdGlvbiI6IjxwPkR1cmluZyBtZWV0aW5ncyBvZiB5b3VuZyBtYXRoZW1hdGljaWFucyBhIGZyZXF1ZW50IHBhc3RpbWUgaXMgdGhlIFByaW1lIE51bWJlciBDaXJjbGUuIEZvciB0aGlzIHRhc2ssIHdlIHJlZmVyIHRvIG1hdGhlbWF0aWNpYW5zIGluIHRoZSBjaXJjbGUgd2l0aCBudW1iZXJzIDEgdG8gTi4mbmJzcDs8XC9wPlxyXG5cclxuPHA+QmVmb3JlIHRoZSBnYW1lIHN0YXJ0cyB3ZSBmaXJzdCBkcmF3IE4tMSBjaXJjbGVzIGFuZCBvbmUgc3F1YXJlIG9uIHRoZSBwYXZlbWVudCBhcnJhbmdlZCBpbiBhIGJpZyBjaXJjbGUuIFRoZSBwbGF5ZXIgbnVtYmVyZWQgMSBzdGFuZHMgaW4gdGhlIHNxdWFyZS4gQWxsIG90aGVyIHBsYXllcnMgc3RhbmQgaW4gdGhlIGNpcmNsZXMsIHN0YXJ0aW5nIHdpdGggdGhlIHBsYXllciAyIGluIGEgY291bnRlcmNsb2Nrd2lzZSBmYXNoaW9uIGZhY2luZyB0b3dhcmRzIHRoZSBtaWRkbGUgb2YgdGhlIGJpZyBjaXJjbGUuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoZSBnYW1lIGNvbnNpc3RzIG9mIEsgcm91bmRzLiBJbiB0aGUgaS10aCByb3VuZCB0aGUgcGVyc29uIHN0YW5kaW5nIGluIHRoZSBzcXVhcmUganVtcHMgdXAsIHNheXMgJnF1b3Q7SXQmIzM5O3MgbWUhJnF1b3Q7IGFuZCB0aGVuIHN3YXBzIHBsYWNlcyB3aXRoIHRoZSBwZXJzb24gc3RhbmRpbmcgb24gaGlzIHJpZ2h0IHNpZGUgcDxzdWI+aTxcL3N1Yj4gdGltZXMsIHdoZXJlIHA8c3ViPmk8XC9zdWI+IGlzIHRoZSBpLXRoIHByaW1lLiBGb3IgZXhhbXBsZSBmb3IgTiA9IDUgYW5kIEsgPSAzIHRoZSBmb2xsb3dpbmcgdGhyZWUgcm91bmRzIG9jY3VyOiZuYnNwOzxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL3ByaW1lY3ljbGUucG5nXCIgc3R5bGU9XCJoZWlnaHQ6MzUycHg7IHdpZHRoOjY3MnB4XCIgXC8+PFwvcD5cclxuXHJcbjxwPldyaXRlIGEgcHJvZ3JhbSB0aGF0IHdpbGwgZm9yIGdpdmVuIE4sIEsgYW5kIEEgZGV0ZXJtaW5lIHRoZSBuZWlnaGJvdXJzIG9mIHRoZSBwbGF5ZXIgbnVtYmVyZWQgQSBhdCB0aGUgZW5kIG9mIHRoZSBnYW1lLiZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGFuZCBvbmx5IGxpbmUgY29udGFpbnMgdGhyZWUgaW50ZWdlcnMgTiwgSyBhbmQgQS4gKDEgJmxlOyBBICZsZTsgTiksIHRoZSBudW1iZXIgb2YgcGxheWVycywgcm91bmRzIGFuZCB0aGUgc2VsZWN0ZWQgcGxheWVyLiZuYnNwOygzICZsZTsgTiAmbGU7IDUgMDAwIDAwMCwgMSAmbGU7IEsgJmxlOyA1MDAgMDAwKS48XC9wPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+VGhlIGZpcnN0IGFuZCBvbmx5IGxpbmUgb2Ygb3V0cHV0IHNob3VsZCBjb250YWluIHR3byBpbnRlZ2VycywgdGhlIG51bWJlcnMgb24gdGhlIHJpZ2h0IGFuZCBsZWZ0IG5laWdoYm91cnMgb2YgdGhlIHBsYXllciBudW1iZXJlZCBBIGF0IHRoZSBlbmQgb2YgdGhlIGdhbWUuJm5ic3A7PFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d

출처

Olympiad > Croatian Highschool Competitions in Informatics > 2010 > Croatian Olympiad in Informatics 2010 2번