Final Ranking

Time limit1sMemory limit128 MB

Summary

Given n students, total score p, and exactly d distinct scores among the top k, output the lexicographically greatest non-increasing score list of non-negative integers, or report that none exists.

Level: Medium6 of 10
Topics: Greedy, Implementation, Math, Brute force
Solved: No attempts yet

Problem

Hongjun is a math teacher at a high school. $n$ students took the final exam, and a student with a higher score is ranked higher.

Grading is finished, but Hongjun only tells the students two facts.

The sum of every student's score is $p$ .
Looking at the scores of the top $k$ ranked students, the number of distinct scores is exactly $d$ .

Each score is a non-negative integer, and when the students are listed from the highest rank to the lowest the scores are non-increasing (equal scores are allowed). Reconstruct a score list consistent with this information.

Because several lists may satisfy the constraints, output the one that is lexicographically greatest when read from the highest-ranked student. That is, make the score of rank $1$ as large as possible, then the score of rank $2$ as large as possible, and so on.

Input

The first line contains four space-separated integers $n$ , $p$ , $k$ , $d$ .

$1 \le k \le n \le 1000$
$0 \le p \le 1{,}000{,}000$
$1 \le d \le k$

Output

Print the lexicographically greatest valid score list, one score per line, from the highest-ranked student to the lowest.

If no score list can be built from the given values, print "Wrong information".

Examples3

Example 1
Input
```
3 4 2 2
```
Expected output
```
4
0
0
```
Example 2
Input
```
3 5 2 2
```
Expected output
```
5
0
0
```
Example 3
Input
```
2 5 2 1
```
Expected output
```
Wrong information
```