Mousetrap (Large Input)

Mousetrap is a card game for one player. The deck holds $K$ cards numbered 1 through $K$, stacked face down. You reveal the top card of the deck, put that card on the bottom, and keep count of how many cards you have revealed. The first card you reveal is counted as 1. If the number on the revealed card equals the current count, you remove that card from the deck and reset the count, so the next card you reveal is counted as 1 again. If the count reaches $K+1$, you lose. If the deck runs out of cards, you win.

Play a deck of 5 cards that reads 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 matches the count, so you remove the 3 and reset the count. The four remaining cards read 1, 4, 2, 5 from the top. You reveal the 1 on count 1 and remove it as well. Going on the same way you remove the 2, then the 4, then the 5, and you win.

A deck is perfect if playing the game with it wins and the removed cards come out in increasing order 1, 2, $\dots$, $K$. With 4 cards the deck 1, 4, 2, 3 is perfect, because the cards come out in the order 1, 2, 3, 4. For every $K$ there is exactly one perfect deck of size $K$, so the card at each position is determined.

Report which card sits at each of several positions of the perfect deck of size $K$.

The first line contains the number of test cases $T$. Each test case is two lines. The first line contains $K$, the number of cards in the deck. The second line contains an integer $n$, followed by $n$ integers $d_1, d_2, \dots, d_n$, the positions you are asked about. Position 1 is the top card of the deck and position $K$ is the bottom card.

• $1 \le T \le 10$
• $1 \le K \le 10^6$
• $1 \le n \le 100$
• $1 \le d_i \le K$

The positions inside one test case need not be distinct and need not be sorted.

Print one line for each test case. Print Case #x: first, then $n$ integers $k_1, k_2, \dots, k_n$ separated by single spaces. Here $x$ is the test case number starting from 1, and $k_i$ is the number of the card at position $d_i$ of the perfect deck of size $K$. Put exactly one space after the colon as well.