Fractiles (Large)

Long ago, the Fractal civilization created artwork consisting of linear rows of tiles. They had two types of tile that they could use: gold (G) and lead (L).

Each piece of Fractal artwork is based on two parameters: an original sequence of K tiles, and a complexity C. For a given original sequence, the artwork with complexity 1 is just that original sequence, and the artwork with complexity X+1 consists of the artwork with complexity X, transformed as follows:

• replace each L tile in the complexity X artwork with another copy of the original sequence
• replace each G tile in the complexity X artwork with K G tiles

For example, for an original sequence of LGL, the pieces of artwork with complexity 1 through 3 are:

• C = 1: LGL (which is just the original sequence)
• C = 2: LGLGGGLGL
• C = 3: LGLGGGLGLGGGGGGGGGLGLGGGLGL

You have just discovered a piece of Fractal artwork, but the tiles are too dirty for you to tell what they are made of. Because you are an expert archaeologist familiar with the local Fractal culture, you know the values of K and C for the artwork, but you do not know the original sequence. Since gold is exciting, you would like to know whether there is at least one G tile in the artwork. Your budget allows you to hire S graduate students, each of whom can clean one tile of your choice (out of the $K^C$ tiles in the artwork) to see whether the tile is G or L.

Is it possible for you to choose a set of no more than S specific tiles to clean, such that no matter what the original pattern was, you will be able to know for sure whether at least one G tile is present in the artwork? If so, which tiles should you clean? Because many sets can work, you must print the one set described in the output section.

The first line of the input gives the number of test cases, T. T test cases follow. Each consists of one line with three integers: K, C, and S.

Limits

• $1 \le T \le 100$
• $1 \le K \le 100$
• $1 \le C \le 100$
• $K^C \le 10^{18}$
• $1 \le S \le K$

For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1). The tile positions are numbered from 1 for the leftmost tile to $K^C$ for the rightmost tile.

If no set of at most S tiles answers your question, y is IMPOSSIBLE. Otherwise y is the list of positions $p_1, p_2, \ldots, p_m$ defined below, in this order (which is increasing), separated by single spaces.

Let $m = \lceil K / C \rceil$. For each $j = 1, 2, \ldots, m$, let $s_j = \min((j-1)C + 1,\ K - C + 1)$, and for each $t = 1, 2, \ldots, C$ let $a_{j,t} = \max(1,\ s_j + t - 1)$. The $j$-th position is

$p_j = 1 + \sum_{t=1}^{C} (a_{j,t} - 1) \cdot K^{C-t}.$

$p_j$ is the tile you reach by taking the $a_{j,1}$-th tile of the complexity 1 artwork and then, at each following complexity, the $a_{j,t}$-th tile inside the block that the previous tile became. Whenever some set of at most S tiles answers the question, $p_1, p_2, \ldots, p_m$ is also such a set.

In sample case #1, there are four possible original sequences: GG, GL, LG, and LL. They would produce the following artwork, respectively:

• Original sequence GG: GGGGGGGG
• Original sequence GL: GGGGGGGL
• Original sequence LG: LGGGGGGG
• Original sequence LL: LLLLLLLL

Looking at tile #2 is enough. If tile #2 turns out to be G, then you know for sure the artwork contains at least one G. (You do not know whether the original sequence is GG, GL, or LG, but that does not matter.) If tile #2 turns out to be L, then the original sequence must be LL, so there are no Gs in the artwork. Here $m = 1$, $s_1 = 0$, $(a_{1,1}, a_{1,2}, a_{1,3}) = (1, 1, 2)$, and $p_1 = 2$.

Looking at tile #1 alone would not be enough. If it turns out to be L, the original sequence could be either LG or LL. With LG the artwork has a G, but with LL it has none.

In sample case #2, the artwork consists of only one tile: either G or L. Looking at that tile tells you whether the artwork has a G in it.

In sample case #3, the artwork is GG, GL, LG, or LL. You can only look at one tile, and neither tile on its own answers the question. If you see L for tile #1, the artwork could be LG or LL. If you see L for tile #2, the artwork could be GL or LL.

Sample case #4 is like sample case #3, but with access to one more tile. Now you can look at the entire artwork.

In sample case #5, there are eight possible original sequences, and they would produce the following artwork:

• Original sequence GGG: GGGGGGGGG
• Original sequence GGL: GGGGGGGGL
• Original sequence GLG: GGGGLGGGG
• Original sequence GLL: GGGGLLGLL
• Original sequence LGG: LGGGGGGGG
• Original sequence LGL: LGLGGGLGL
• Original sequence LLG: LLGLLGGGG
• Original sequence LLL: LLLLLLLLL

Tiles #2 and #6 answer the question. If both turn out to be L, the artwork must be all Ls. Otherwise there is at least one G. Tiles #1 and #2 would not work, because even if both are L, the original sequence could still be LLG.