Construct a Valid Brick Placement Sequence

Given four integers \(n\), \(m\), \(k\), and \(S\), your task is to construct a sequence \(a = [a_1, a_2, \dots, a_n]\) of length \(n\) that satisfies the following conditions:

• \(0 \le a_i \le m\) for all \(1 \leq i \leq n\);
• \(|a_i - a_{i-1}| \le k\) for every \(2 \leq i \leq n\);
• \(\sum_{i=1}^{n} a_i = S\).

This problem is inspired by a brick placement scenario. Imagine a grid with \(n\) columns and \(m+1\) rows. You have exactly \(S\) bricks (each of size \(1 \times 1\)) that must be placed on the grid. Due to gravity, a brick can only be placed on the bottom or directly on top of another brick. In addition, to ensure that the character can move between adjacent columns, the difference in the number of bricks between any two consecutive columns must not exceed \(k\). It is guaranteed that a valid configuration exists.

inputFormat

The input consists of a single line containing four space-separated integers: \(n\), \(m\), \(k\), and \(S\).

outputFormat

Output a sequence of \(n\) integers \(a_1, a_2, \dots, a_n\) separated by spaces, where \(a_i\) denotes the number of bricks in the \(i\)-th column.

sample

3 3 1 5

2 2 1