407015: GYM102687 B Racoon Virus

In an alternate universe, a virus carried primarily by raccoons has spread worldwide. To develop a vaccine, scientists are studying its RNA makeup.

In this universe, RNA (Racoon Nucleic Acid) is constructed rather differently. An $$$m$$$-length RNA strand can be represented by an array of $$$m$$$ nonnegative integers $$$A_i$$$. A substrand of a RNA strand is any nonempty contiguous subarray of this RNA strand. Two substrands are said to be compatible if the sum of their elements are equal. The infection index of a RNA strand is the maximum size of a set containing only its substrands, such that no two elements in the set are compatible.

To help in the research of the virus, the Pandemic Research Committee (PRC) has teamed up with the National Overseer Institute on Pandemic Havocs (NOI PH). Together, they discovered that the virus is an $$$n$$$-length RNA strand with infection index $$$k$$$. They also discovered that all elements making up the virus strand never exceeded $$$10^9$$$. However, after these discoveries, they are running low on virus samples to research with.

As a member of the final selection pool of interns working in the NOI PH, you realized this was the perfect opportunity to prove your worth! You decide to try and reconstruct the virus with what is known to make more samples. If you succeed, you may even be invited to intern in the International Overseer of Infections (IOI)! Do your best!

Note that the information obtained on the virus may have also been miscalculated, and a RNA strand with its characteristics may be inconstructible. If this is the case, you must also say so.

The first line of input contains $$$t$$$, the number of test cases. Then $$$t$$$ lines follow, each containing two space separated integers $$$n$$$ and $$$k$$$.

For each given $$$n$$$ and $$$k$$$, output a single line containing

• "POSSIBLE" (without the quotes) if there exists a length-$$$n$$$ RNA strand with infection index $$$k$$$ where every element $$$A_i$$$ is a nonnegative integer between $$$0$$$ and $$$10^9$$$ (inclusive), and
• "IMPOSSIBLE" (without the quotes) if it does not exist.

In addition, if you outputted POSSIBLE, print a second line containing $$$n$$$ space-separated integers $$$A_1, A_2, \ldots, A_n$$$ denoting the elements of the length-$$$n$$$ RNA strand.

If there are several answers, output any.

For all subtasks

$$$1 \le t \le 10000$$$

$$$1 \le n \le 1000$$$

$$$1 \le k \le 10^6$$$

The sum of $$$n^2$$$ across all test cases in a file is $$$\le 10^7$$$

Subtask 1 (16 points): $$$n < 30$$$

Subtask 2 (17 points): $$$n \le 50$$$

Subtask 3 (15 points): $$$n \le 100$$$

Subtask 4 (14 points): $$$n \le 200$$$

Subtask 5 (15 points): $$$n \le 400$$$

Subtask 6 (9 points): $$$n \le 750$$$

Subtask 7 (14 points): No additional constraints.

2
1 2
3 4

IMPOSSIBLE
POSSIBLE
2 1 2

Sample case $$$1$$$: We have $$$n = 1$$$. It is impossible to create a $$$1$$$-length RNA strand with infection index $$$k=2$$$, so we output IMPOSSIBLE.

Sample case $$$2$$$: We have $$$n = 3$$$. One $$$3$$$-length RNA strand that has infection index $$$k=4$$$ is 2 1 2. An example set of four substrands in this strand are $$$[1]$$$, $$$[2]$$$, $$$[1, 2]$$$, and $$$[2, 1, 2]$$$. Note that $$$[2, 1]$$$ and $$$[1, 2]$$$ are compatible because their element sums are the same, and hence cannot both be in this set. $$$[2, 2]$$$ is not a substrand because it is not contiguous. Other solutions exist such as 1 1 2, and you may output any.