Background

Problem Description

Brief Statement

Given $n, m, k, S$, construct an integer sequence $a$ of length $n$ such that:

• $0 \leqslant a_i \leqslant m, \forall i \in [1, n]$ (each element of $a$ is at least $0$ and at most $m$).
• $|a_i - a_{i-1}| \leqslant k, \forall i \in (1, n]$ (for every two adjacent elements in $a$, the absolute difference is at most $k$).
• $(\sum_{i=1}^n a_i) = S$ (the sum of all elements in $a$ is $S$).

A solution is guaranteed to exist.

Original Statement

I forgot what happened before, but you followed kid and traveled to ic (I wanna be the Creator) and arrived in front of a level editor. The map has width $n$ and height $(m+1)$, and you cannot change these. There are also $S$ unplaced $1 \times 1$ bricks. Now you need to help kid place them, meaning: place these $S$ bricks so that kid can pass. The requirements are:

1. Bricks have gravity, so a brick can only be placed on the bottom boundary or on top of another brick. You cannot place multiple bricks at the same $(x, y)$ coordinate.
2. You must leave at least one gap for kid to pass, so in each column you can place at most $m$ bricks (since the map height is $m+1$). Note that in ic levels, the bottom boundary does not cause damage, so a column may also have no bricks.
3. kid’s jumping ability and the ability to fall from a height without getting hurt are limited, described by a non-negative integer $k$: the absolute difference between the numbers of bricks placed in adjacent columns cannot exceed $k$, otherwise the level is impossible for kid. ((But note: this rule does not restrict the height of the first column, since kid’s spawn point is in the first column.))
4. You must place all $S$ bricks, no more and no less.

Creator will not make things difficult for you, so there is always a level that satisfies all the rules above.

For easier output, you only need to give how many bricks are in the $i$-th column (denote it as $a_i$), i.e., output the sequence $a$. It is easy to prove that a valid sequence $a$ corresponds one-to-one with a valid level.

Input Format

A single line with $4$ non-negative integers $n, m, k, S$.

Output Format

Output one line with $n$ non-negative integers representing your constructed sequence $a$. If there are multiple possible sequences, output any one that satisfies the requirements. It is guaranteed that at least one sequence satisfies the requirements.

4 6 2 11

2 4 2 3

3 4 5 6

4 2 0

Hint

Constraints

This problem has $10$ test points, equally weighted.

• For $20\%$ of the testdata, $S = n \cdot m$.
• For $20\%$ of the testdata, $k = 0$.
• For $20\%$ of the testdata, $k = 10^9$.

For $100\%$ of the testdata, $1 \leqslant n, m \leqslant 10^5$, $0 \leqslant k \leqslant 10^9$, $0 \leqslant S \leqslant n \cdot m$.

Hint

In ancient times there was a number, its name was $S$. $S$ can be so large that one int may (possibly) not hold it.

Sample Explanation #1

The level corresponding to the sample output is as follows.

Note that there may be multiple valid levels that meet the conditions.

Translated by ChatGPT 5