Analysis: The Bessie Shuffle (gold) by Bruce Merry

This problem is not conceptually difficult once the basic mechanism has been found, but it requires careful thought to implement correctly as there are a number of cases.

The first trick is to note that removing the top card can be seen as replacing one card in the window of M cards then rotating by one. Combining the given permutation P with this rotation gives the true permutation that operates on the window of M cards.

A standard tool for operating on permutations is to identify the cycles i.e. pick a number x and examine x, P[x], P[P[x]], P[P[P[x]]] etc until it repeats. Once the cycles have been identified, it becomes possible to, in O(1), determine how many iterations are needed for a card to move from one position to another under the permutation, or to determine where a card will end up after an arbitrary number of iterations.

The queries ask which card ends up in a given position, rather than which position a given card finishes in, so we need to think about everything in reverse. We start with the query card position, and follow the card backwards through time to find out which position it came from, and hence what its number is. There are two cases for initializing the process

1. The card is one of the first M-1 cards in the output. In this case we can determine its position immediately before the first permutation (here "before" and "first" are in our backwards version of time).
2. Otherwise, the card was taken from the output stack and placed into the window after a known number of permutations.

When considering the evolution of this card, there are again two cases. Either it eventually reaches the bottom of the window and is moved to the input pile, or it doesn't and ends up as one of the top M-1 cards on the input stack.