Broot

Time Limit: 2000/1000 MS (Java/Others)

Memory Limit: 128000/128000 K (Java/Others)

Description

There is a way of encryption in the Digital planet. If the number x, who lives in M area, K layer, then it will change its name to x ^ K mod M, that is newx = x ^ k mod m. Now the Digital Kingdom wants to make a program, which can find all the original number of a name living in some area, some layer. If there is no solution, output -1.

Input

There are multiply test cases. Each test case contains there integers k, m , newx ,(0 <= newx , m ,k <= 1.5*10^15) , m is a prime number.

Output

For each test case, you should output some lines, the format of the first line is: “caseN:” (N is the label of test case). Then next lines each contain a number x, output x as ascending order. (0 <= x < m)

Sample Input

1 5 4 2 13 8 3 13 8

Sample Output

case1: 4 case2: -1 case3: 2 5 6

Hint

Source

2011 Multi-University Training Contest 10 -

提交代码