26417번 - Range Partition 서브태스크스페셜 저지다국어

Alan and Barbara suddenly felt like playing with numbers. Alan chooses a non-empty subset from the set of first $N$ positive integers ($1,2,\dots ,N$). Barbara takes the rest of the numbers (if any) from the set. And then they both calculate the sum of the elements in their respective sets.

Alan believes in a magic ratio, which is $X:Y$. Hence, Alan wants to choose the subset in such a way that the ratio between the sum of Alan's subset and the sum of Barbara's subset is exactly $X:Y$.

Can you help Alan to choose a subset that can achieve the desired ratio?

The first line of the input gives the number of test cases, $T$. $T$ test cases follow.

Each test case has a single line containing three integers, $N$, $X$ and $Y$, as described above.

For each test case, output the first line containing Case #x: y, where $x$ is the test case number (starting from 1) and $y$ is POSSIBLE, if Alan can choose such a non-empty subset, and IMPOSSIBLE otherwise.

If you print POSSIBLE, then output two more lines for that test case.

In the second line, print a single integer, which denotes the size of Alan's subset.

In the third line, print the integers present in Alan's subset.

If there are multiple solutions, you can print any of them.

• $1≤T≤100$.
• $1≤X≤10^8$.
• $1≤Y≤10^8$.
• $\gcd(X,Y)=1$, where gcd is Greatest common divisor.

• $1≤N≤15$.

• $1≤N≤5000$.