Mousetrap (Small)

Mousetrap is a simple card game for one player. You start with $K$ cards numbered 1 through $K$, shuffled and stacked face down in a single deck.

One move works like this. Set the count to 1 and reveal the top card of the deck. If its number equals the current count, remove that card from the deck and reset the count to 1. Otherwise move that card to the bottom of the deck and increase the count by 1. If the count ever reaches $K+1$, you lose. If you remove every card, you win.

Consider a deck of 5 cards holding 2, 5, 3, 1, 4 from the top. You reveal the 2 on count 1, the 5 on count 2, and the 3 on count 3. The number equals the count, so you remove the 3 and reset the count to 1. The four remaining cards read 1, 4, 2, 5 from the top. You reveal the 1 on count 1 and remove it right away, and in the same way you go on to remove the 2, the 4 and the 5 for a win.

Now work in the other direction and lay out the deck yourself. Call a deck perfect if it wins the game and the cards leave in numerical order, that is 1, then 2, then 3, on up to $K$. With 4 cards, the arrangement 1, 4, 2, 3 from the top wins and removes the cards in the order 1, 2, 3, 4.

Once $K$ is fixed, the perfect deck is determined. Index 1 of the deck is the top card and index $K$ is the bottom card. Report which card sits at a given index of the perfect deck.

The first line contains the number of test cases $T$.

Each test case takes two lines. The first line contains $K$, the number of cards in the deck. The second line contains the number of queries $n$, followed by the deck indices $d_1, d_2, \dots, d_n$ separated by spaces.

Limits

• $1 \le T \le 100$
• $1 \le K \le 5000$
• $1 \le n \le 100$
• $1 \le d_i \le K$

For each test case, print one line starting with Case #x: and then the $n$ integers $k_1, k_2, \dots, k_n$. Here $x$ is the test case number counted from 1, and $k_i$ is the number of the card at index $d_i$ of the perfect deck of size $K$.

Put exactly one space after the colon and separate the printed integers with one space each.