print1639. Prime Number Circle

printPrime Number Circle

Ограничения: время – 3s/6s, память – 32MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

During meetings of young mathematicians a frequent pastime is the Prime Number Circle. For this task, we refer to mathematicians in the circle with numbers 1 to `N`.
Before the game starts we first draw `N-1` circles and one square on the pavement arranged in a big circle. The player numbered 1 stands in the square. All other players stand in the circles, starting with the player 2 in a counterclockwise fashion facing towards the middle of the big circle.
The game consists of `K` rounds. In the `i`-th round the person standing in the square jumps up, says "It's me!" and then swaps places with the person standing on his right side `p_k` times, where `p_k` is the `k`-th prime. For example for `N\ =\ 5` and `K\ =\ 3` the following three rounds occur:

15004.png

Input
The first and only line contains three integers `N`, `K` and `A` (`1\ ≤\ A\ ≤\ N`, `3\ ≤\ N\ ≤\ 5\ 000\ 000`, `1\ ≤\ K\ ≤\ 500\ 000`), the number of players, rounds and the selected player.
Output
The first and only line of output should contain two integers, the numbers on the right and left neighbours of the player numbered `A` at the end of the game.

Sample Input 1

5 3 1

Sample Output 1

3 5

Sample Input 2

5 3 2

Sample Output 2

5 4

Sample Input 3

5 4 5 

Sample Output 3

3 2
Source: COCI 2009/2010, final contest
loading