Training Site
Sideways banner 8b44c02b768aa359c4d0a2bce3b247c6d7ab888f8b26852e9bfc3659c8c25612

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.

Subtasks

  • 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