시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB144352452.174%

문제

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

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

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

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

  1. 라운드: 
  2. 라운드: 
  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

예제 입력 2

5 3 2

예제 출력 2

5 4

예제 입력 3

5 4 5

예제 출력 3

3 2
W3sicHJvYmxlbV9pZCI6IjI4ODIiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWMxOGNcdWMyMTggXHVjMGFjXHVjNzc0XHVkMDc0IiwiZGVzY3JpcHRpb24iOiI8cD5cdWMwYzFcdWFkZmNcdWM3NzRcdWM2NDAgXHVjZTVjXHVhZDZjXHViNGU0XHVjNzc0IFx1YzIyMFx1Yzc5MFx1YjlhY1x1YzVkMFx1YzExYyBcdWQ1NThcdWIyOTQgXHVhYzhjXHVjNzg0XHVjNzQwIFx1YzE4Y1x1YzIxOCBcdWMwYWNcdWM3NzRcdWQwNzQgXHVhYzhjXHVjNzg0XHVjNzc0XHViMmU0LiBcdWFjMDEgXHVjMGFjXHViNzhjXHVjNzQwIDFcdWJjODhcdWJkODBcdWQxMzAgTlx1YmM4OFx1YzczY1x1Yjg1YyBcdWIwOThcdWQwYzBcdWIwYjhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWM4Y1x1Yzc4NFx1Yzc0NCBcdWMyZGNcdWM3OTFcdWQ1NThcdWFlMzBcdWM1ZDAgXHVjNTVlXHVjMTFjIFx1YjNkOVx1YWRmOFx1Yjc4MCBcdWM3NThcdWM3OTAgTi0xXHVhYzFjXHVjNjQwIFx1YjEyNFx1YmFhOFx1YjA5YyBcdWM3NThcdWM3OTAgMVx1YWMxY1x1Yjk3YyBcdWM5MDBcdWJlNDRcdWQ1NWNcdWIyZTQuIFx1Yzc1OFx1Yzc5MFx1YjI5NCBcdWM2ZDBcdWM3NDQgXHVjNzc0XHViOGU4XHVjNWI0XHVjMTFjIFx1YmMzMFx1Y2U1OFx1ZDU1Y1x1YjJlNC4gXHViYTNjXHVjODAwLCAxXHViYzg4XHVjNzc0IFx1YjEyNFx1YmFhOFx1YjA5YyBcdWM3NThcdWM3OTBcdWM1ZDAgXHVjNTQ5XHVhY2UwLCBcdWIyZTRcdWM3NGMgMlx1YmM4OFx1YmQ4MFx1ZDEzMFx1YjI5NCBcdWJjMThcdWMyZGNcdWFjYzRcdWJjMjlcdWQ1YTVcdWM3M2NcdWI4NWMgXHVjYzI4XHViODQwXHViMzAwXHViODVjIFx1Yzc1OFx1Yzc5MFx1YzVkMCBcdWM1NDlcdWIyOTRcdWIyZTQuIFx1YmFhOFx1YjRlMCBcdWMwYWNcdWI3OGNcdWM3NDAgXHVjNmQwXHVjNzU4IFx1YzkxMVx1YzJlY1x1Yzc0NCBcdWJjMTRcdWI3N2NcdWJjZjRcdWFjZTAgXHVjNzg4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWFjOGNcdWM3ODRcdWM3NDAgXHVjZDFkIEtcdWFjMWMgXHViNzdjXHVjNmI0XHViNGRjXHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuIGlcdWJjODhcdWM5ZjggXHViNzdjXHVjNmI0XHViNGRjIFx1YzJkY1x1Yzc5MVx1YjQxOFx1YmE3NCBcdWIxMjRcdWJhYThcdWM1ZDAgXHVjNTQ5XHVjNzQwIFx1YzBhY1x1Yjc4Y1x1Yzc3NCBcdWM3OTBcdWI5YWNcdWM1ZDBcdWMxMWMgXHVjNzdjXHVjNWI0XHViMDk4XHVjMTFjICZxdW90O1x1YjBiNFx1YWMwMCBcdWIxMjRcdWJhYThcdWM1N2MhJnF1b3Q7XHViNzdjXHVhY2UwIFx1YzY3OFx1Y2U1Y1x1YjJlNC4gXHVhZGY4IFx1YjJlNFx1Yzc0YywgXHVjNjI0XHViOTc4XHVjYWJkXHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWMwYWNcdWI3OGNcdWFjZmMgXHVjNzkwXHViOWFjXHViOTdjIFx1Y2QxZCBQPHN1Yj5pPFwvc3ViPlx1YmM4OCBcdWJjMTRcdWFmYjhcdWFjOGMgXHViNDFjXHViMmU0LiBQPHN1Yj5pPFwvc3ViPlx1YjI5NCBpXHViYzg4XHVjOWY4IFx1Yzc5MVx1Yzc0MCBcdWMxOGNcdWMyMThcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YzU0NFx1Yjc5OFx1YjI5NCBOPTUsIEs9M1x1Yzc3OCBcdWM2MDhcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxvbD5cclxuXHQ8bGk+XHViNzdjXHVjNmI0XHViNGRjOiZuYnNwOzxpbWcgYWx0PVwiXCIgc3JjPVwiaHR0cHM6XC9cL3VwbG9hZC5hY21pY3BjLm5ldFwvZThlOWFhMmYtYzJmYS00ZmZmLWFjODAtODFiNTEyN2EyOWE0XC8tXC9wcmV2aWV3XC9cIiBzdHlsZT1cIndpZHRoOiAzMjFweDsgaGVpZ2h0OiA4NnB4O1wiIFwvPjxcL2xpPlxyXG5cdDxsaT5cdWI3N2NcdWM2YjRcdWI0ZGM6Jm5ic3A7PGltZyBhbHQ9XCJcIiBzcmM9XCJodHRwczpcL1wvdXBsb2FkLmFjbWljcGMubmV0XC8zNmZjYzc3NC0zYzE0LTQ1NDAtYWY1NC01ZTRhMTQyN2U3ODVcLy1cL3ByZXZpZXdcL1wiIHN0eWxlPVwid2lkdGg6IDQzNnB4OyBoZWlnaHQ6IDg1cHg7XCIgXC8+PFwvbGk+XHJcblx0PGxpPlx1Yjc3Y1x1YzZiNFx1YjRkYzombmJzcDs8aW1nIGFsdD1cIlwiIHNyYz1cImh0dHBzOlwvXC91cGxvYWQuYWNtaWNwYy5uZXRcL2MyMzQwYzQxLWU0ZTAtNGI5Yi1iZTYxLTUzOGZiYzU2N2ZiMVwvLVwvcHJldmlld1wvXCIgc3R5bGU9XCJ3aWR0aDogNjQycHg7IGhlaWdodDogODVweDtcIiBcLz48XC9saT5cclxuPFwvb2w+XHJcblxyXG48cD5OLCBLLCBBXHVhYzAwIFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1YWM4Y1x1Yzc4NFx1Yzc3NCBcdWIwNWRcdWIwOWMgXHVkNmM0XHVjNWQwIEFcdWM3NTggXHVjNzc0XHVjNmMzXHVjNzQ0IFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LiZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBOLCBLLCBBXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDMgJmxlOyBOICZsZTsgNSwwMDAsMDAwLCAxICZsZTsgSyAmbGU7IDUwMCwwMDAsIDEgJmxlOyBBICZsZTsgTik8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWFjOGNcdWM3ODRcdWM3NzQgXHViMDVkXHViMDljIFx1ZDZjNFx1YzVkMCBBXHVjNzU4IFx1YzYyNFx1Yjk3OFx1Y2FiZFx1YzVkMCBcdWM3ODhcdWIyOTQgXHVjMGFjXHViNzhjXHVhY2ZjIFx1YzY3Y1x1Y2FiZFx1YzVkMCBcdWM3ODhcdWIyOTQgXHVjMGFjXHViNzhjXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiIyODgyIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiS09MTyIsImRlc2NyaXB0aW9uIjoiPHA+RHVyaW5nIG1lZXRpbmdzIG9mIHlvdW5nIG1hdGhlbWF0aWNpYW5zIGEgZnJlcXVlbnQgcGFzdGltZSBpcyB0aGUgUHJpbWUgTnVtYmVyIENpcmNsZS4gRm9yIHRoaXMgdGFzaywgd2UgcmVmZXIgdG8gbWF0aGVtYXRpY2lhbnMgaW4gdGhlIGNpcmNsZSB3aXRoIG51bWJlcnMgMSB0byBOLiZuYnNwOzxcL3A+XHJcblxyXG48cD5CZWZvcmUgdGhlIGdhbWUgc3RhcnRzIHdlIGZpcnN0IGRyYXcgTi0xIGNpcmNsZXMgYW5kIG9uZSBzcXVhcmUgb24gdGhlIHBhdmVtZW50IGFycmFuZ2VkIGluIGEgYmlnIGNpcmNsZS4gVGhlIHBsYXllciBudW1iZXJlZCAxIHN0YW5kcyBpbiB0aGUgc3F1YXJlLiBBbGwgb3RoZXIgcGxheWVycyBzdGFuZCBpbiB0aGUgY2lyY2xlcywgc3RhcnRpbmcgd2l0aCB0aGUgcGxheWVyIDIgaW4gYSBjb3VudGVyY2xvY2t3aXNlIGZhc2hpb24gZmFjaW5nIHRvd2FyZHMgdGhlIG1pZGRsZSBvZiB0aGUgYmlnIGNpcmNsZS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VGhlIGdhbWUgY29uc2lzdHMgb2YgSyByb3VuZHMuIEluIHRoZSBpLXRoIHJvdW5kIHRoZSBwZXJzb24gc3RhbmRpbmcgaW4gdGhlIHNxdWFyZSBqdW1wcyB1cCwgc2F5cyAmcXVvdDtJdCYjMzk7cyBtZSEmcXVvdDsgYW5kIHRoZW4gc3dhcHMgcGxhY2VzIHdpdGggdGhlIHBlcnNvbiBzdGFuZGluZyBvbiBoaXMgcmlnaHQgc2lkZSBwPHN1Yj5pPFwvc3ViPiB0aW1lcywgd2hlcmUgcDxzdWI+aTxcL3N1Yj4gaXMgdGhlIGktdGggcHJpbWUuIEZvciBleGFtcGxlIGZvciBOID0gNSBhbmQgSyA9IDMgdGhlIGZvbGxvd2luZyB0aHJlZSByb3VuZHMgb2NjdXI6Jm5ic3A7PFwvcD5cclxuXHJcbjxvbD5cclxuXHQ8bGk+cm91bmQ6Jm5ic3A7PGltZyBhbHQ9XCJcIiBzcmM9XCJodHRwczpcL1wvdXBsb2FkLmFjbWljcGMubmV0XC9lOGU5YWEyZi1jMmZhLTRmZmYtYWM4MC04MWI1MTI3YTI5YTRcLy1cL3ByZXZpZXdcL1wiIHN0eWxlPVwid2lkdGg6IDMyMXB4OyBoZWlnaHQ6IDg2cHg7XCIgXC8+PFwvbGk+XHJcblx0PGxpPnJvdW5kOiZuYnNwOzxpbWcgYWx0PVwiXCIgc3JjPVwiaHR0cHM6XC9cL3VwbG9hZC5hY21pY3BjLm5ldFwvMzZmY2M3NzQtM2MxNC00NTQwLWFmNTQtNWU0YTE0MjdlNzg1XC8tXC9wcmV2aWV3XC9cIiBzdHlsZT1cIndpZHRoOiA0MzZweDsgaGVpZ2h0OiA4NXB4O1wiIFwvPjxcL2xpPlxyXG5cdDxsaT5yb3VuZDombmJzcDs8aW1nIGFsdD1cIlwiIHNyYz1cImh0dHBzOlwvXC91cGxvYWQuYWNtaWNwYy5uZXRcL2MyMzQwYzQxLWU0ZTAtNGI5Yi1iZTYxLTUzOGZiYzU2N2ZiMVwvLVwvcHJldmlld1wvXCIgc3R5bGU9XCJ3aWR0aDogNjQycHg7IGhlaWdodDogODVweDtcIiBcLz48XC9saT5cclxuPFwvb2w+XHJcblxyXG48cD5Xcml0ZSBhIHByb2dyYW0gdGhhdCB3aWxsIGZvciBnaXZlbiBOLCBLIGFuZCBBIGRldGVybWluZSB0aGUgbmVpZ2hib3VycyBvZiB0aGUgcGxheWVyIG51bWJlcmVkIEEgYXQgdGhlIGVuZCBvZiB0aGUgZ2FtZS4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBhbmQgb25seSBsaW5lIGNvbnRhaW5zIHRocmVlIGludGVnZXJzIE4sIEsgYW5kIEEuICgxICZsZTsgQSAmbGU7IE4pLCB0aGUgbnVtYmVyIG9mIHBsYXllcnMsIHJvdW5kcyBhbmQgdGhlIHNlbGVjdGVkIHBsYXllci4mbmJzcDsoMyAmbGU7IE4gJmxlOyA1IDAwMCAwMDAsIDEgJmxlOyBLICZsZTsgNTAwIDAwMCkuPFwvcD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlRoZSBmaXJzdCBhbmQgb25seSBsaW5lIG9mIG91dHB1dCBzaG91bGQgY29udGFpbiB0d28gaW50ZWdlcnMsIHRoZSBudW1iZXJzIG9uIHRoZSByaWdodCBhbmQgbGVmdCBuZWlnaGJvdXJzIG9mIHRoZSBwbGF5ZXIgbnVtYmVyZWQgQSBhdCB0aGUgZW5kIG9mIHRoZSBnYW1lLiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=

출처

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