Training Site

# An Average Problem

Input: Standard Input (stdin)
Output: Standard Output (stdout)
Memory limit: 64 megabytes
Time limit: 2.0 seconds

Determine whether it is possible to generate a sequence of integers $x_1, x_2,\dots,x_N$ ($1 \le x_i \le 1\,000\,000$) that meets the following criteria:

• The number of values is $N$.
• The mean is $A$ (the sum of values divided by the number of values).
• The median is $B$ (the middle value if the sequence is sorted – it is guaranteed that $N$ is odd).
• The mode is $C$ (the most frequent value). Note that there is only one mode – there should not be any other value that occurs as frequently as the mode.

For 60% of the points, you should also output a valid sequence meeting the above criteria (if one exists).

## Input

There will be a single line, containing four space-separated integers: $N$, the number of elements, $A$, the mean, $B$, the median, and $C$, the mode ($1 \le N < 100\,000$, $1 \le A,B,C \le 1\,000\,000$). It is guaranteed that $N$ is odd.

## Output

The first line should contain either Possible or Impossible, representing whether it is possible to generate a valid sequence that meets the above criteria or not.

If it is possible to generate a valid sequence, you may also output a second line containing $N$ space-separated integers in any order, representing a sequence that meets the above criteria. Each element of the sequence should be an integer $x_i$, such that $1 \le x_i \le 1\,000\,000$. If there is more than one possible sequence, you may output any of them.

• Subtask 1 (5%): $A = B = C$
• Subtask 2 (10%): $N = 1 \text{ or } 3$
• Subtask 3 (20%): $B = C$
• Subtask 4 (35%): $N < 1000$
• Subtask 5 (30%): No further restrictions apply.

## Scoring

For each test case:

• If you correctly determine that it is possible to generate a sequence, and do not output a sequence, or output an invalid sequence, you will score 40% for that test case.
• If you correctly determine that it is possible to generate a sequence, and also output a valid sequence, you will score 100% for that test case.
• If you correctly determine that it is impossible to generate a sequence, you will score 100% for that test case.

Your score for each subtask will be the minimum score among all test cases in that subtask.

• ### Sample Input 1

5 7 6 5


### Sample Output 1

Possible
5 5 6 7 12

• ### Sample Input 2

3 5 4 6


### Sample Output 2

Impossible

• ### Sample Input 3

7 8 9 9


### Sample Output 3

Possible
6 7 7 9 9 9 9