Card Shuffle Machine

Run a deck of cards through a card-shuffling machine that repeats the same program many times.

The deck has n cards labelled 0 to n - 1, and starts in that order with card 0 on top. The machine runs a program: a list of steps, each a string, applied in order to the whole deck. One run of the whole program is a pass. The steps are:

• "cut k": let r = k mod n, taken as a non-negative remainder (so -1 behaves like n - 1, and n + 2 like 2). Move the top r cards to the bottom, keeping their order. Equivalently, a negative k moves the bottom |k| mod n cards to the top, keeping their order.
• "flip m": reverse the order of the top min(m, n) cards. The rest of the deck is untouched.
• "weave": split the deck into a top half of the first ceil(n / 2) cards and a bottom half of the rest (so with an odd number of cards the top half is one larger). Then interleave them, starting with the top half's first card: top 1st, bottom 1st, top 2nd, bottom 2nd, and so on. A deck of 1 card is unchanged.
• "deal s": deal the deck from the top, one card at a time, into s piles numbered 0 to s - 1: the card at position i (counting from 0) goes face-up on top of pile i mod s. Then pick the piles up one after another, pile 0 first, each read from its top card to its bottom card, and that sequence is the new deck from the top down. (If s > n the extra piles are empty. Note that each pile is the reverse of the order its cards were dealt in; deal 1 therefore reverses the whole deck.)

The program is repeated times times, one pass after another, on the same deck. The number of passes is huge, so you cannot simulate them one by one.

Input: n, the number of cards; program, a list of step strings; times, the number of passes.

Output: the deck after all passes, as a list of card labels from the top card to the bottom card. With times = 0 or an empty program the deck is unchanged.