P2054 [AHOI2005] Shuffle

To recognize Xiao Lian’s contributions to the exploration of Planet Samuel, he was invited to participate in a close-range manned expedition to Planet Samuel. Because Planet Samuel is very far away, the scientists will spend a long time on the spaceship. Xiao Lian suggested playing poker to pass the time during the long trip. After a few rounds, everyone felt that simply playing poker was too easy for people as intelligent as they were. Someone proposed a new way to play with the cards. A shuffle is defined as follows: split a deck of $N$ cards (where $N$ is even) evenly into an upper half and a lower half. Take the first card from the lower half as the first card of the new deck, then take the first card from the upper half as the second card of the new deck, then take the second card from the lower half as the third card, and so on, alternating until all cards are taken. If we take a deck of 6 cards {1, 2, 3, 4, 5, 6}, the process of one shuffle is shown below:  From the figure, we can see that after one shuffle, the sequence 1, 2, 3, 4, 5, 6 becomes 4, 1, 5, 2, 6, 3. Of course, shuffling the resulting sequence once more yields 2, 4, 6, 1, 3, 5. The game is as follows: given a deck of length $N$, with face values increasing continuously from 1 to $N$ (suits ignored), perform $M$ shuffles on this deck. The scientist who first says the face value of the $L$-th card in the sequence after shuffling wins. Xiao Lian wants to win the game. Can you help him?

The input file contains three integers separated by spaces, representing $N, M, L$. (Where $1 \le N \le 10^{10}$, $0 \le M \le 10^{10}$, and $N$ is even.)

Output the face value of the specified card on a single line.

$0 < N \le 10^{10}$, $0 \le M \le 10^{10}$, and $N$ is even. Translated by ChatGPT 5