Modular Sequence
Contest: Codeforces Round 924 (Div. 2)
Difficulty rating: 2300
Tags: brute force, constructive algorithms, dp, graphs, greedy, math, number theory

You are given two integers $$$x$$$ and $$$y$$$. A sequence $$$a$$$ of length $$$n$$$ is called modular if $$$a_1=x$$$, and for all $$$1 < i \le n$$$ the value of $$$a_{i}$$$ is either $$$a_{i-1} + y$$$ or $$$a_{i-1} \bmod y$$$. Here $$$x \bmod y$$$ denotes the remainder from dividing $$$x$$$ by $$$y$$$.

Determine if there exists a modular sequence of length $$$n$$$ with the sum of its elements equal to $$$S$$$, and if it exists, find any such sequence.

Input format:
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 2 \cdot 10^4$$$). The description of the test cases follows.

The first and only line of each test case contains four integers $$$n$$$, $$$x$$$, $$$y$$$, and $$$s$$$ ($$$1 \le n \le 2 \cdot 10^5$$$, $$$0 \le x \le 2 \cdot 10^5$$$, $$$1 \le y \le 2 \cdot 10^5$$$, $$$0 \le s \le 2 \cdot 10^5$$$) — the length of the sequence, the parameters $$$x$$$ and $$$y$$$, and the required sum of the sequence elements.

The sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$, and also the sum of $$$s$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output format:
For each test case, if the desired sequence exists, output "Yes" on the first line (without quotes). Then, on the second line, output $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ separated by a space — the elements of the sequence $$$a$$$. If there are multiple suitable sequences, output any of them.

If the sequence does not exist, output "No" on a single line.

You can output each letter in any case (lowercase or uppercase). For example, the strings "yEs", "yes", "Yes", and "YES" will be accepted as a positive answer.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first example, the sequence $$$[8, 11, 2, 5, 2]$$$ satisfies the conditions. Thus, $$$a_1 = 8 = x$$$, $$$a_2 = 11 = a_1 + 3$$$, $$$a_3 = 2 = a_2 \bmod 3$$$, $$$a_4 = 5 = a_3 + 3$$$, $$$a_5 = 2 = a_4 \bmod 3$$$.

In the second example, the first element of the sequence should be equal to $$$5$$$, so the sequence $$$[2, 2, 2]$$$ is not suitable.

Example input:
3
5 8 3 28
3 5 3 6
9 1 5 79

Example output:
YES
8 11 2 2 5 
NO
NO

Editorial:
Let's see what the answer will look like: first, there will be a prefix of the form $$$x, x + y, \ldots, x + k\cdot y$$$, and then there will be some number of blocks of the form $$$x \bmod y, x \bmod y + y, \ldots, x \bmod y + k \cdot y$$$.
We can subtract the number $$$x \bmod y$$$ from all the elements of the sequence, and then divide all the elements by $$$y$$$ (all the elements will be divisible by $$$y$$$, since they initially had a remainder of $$$x \bmod y$$$). Let $$$b_1 = \frac{x - x \bmod y}{y}$$$. Then our sequence will start with $$$b_1, b_1 + 1, \ldots, b_1 + k_1$$$, and then there will be blocks of the form $$$0, 1, \ldots, k_i$$$.
Let's calculate these values: $$$dp_i$$$ — the minimum length of a sequence of blocks of the form $$$0, 1, \ldots, k_j$$$ with a sum of $$$i$$$. This value can be calculated for all numbers from $$$0$$$ to $$$s$$$ using dynamic programming. If we have processed all values from $$$0$$$ to $$$k-1$$$, then for $$$k$$$ we have calculated the minimum length, and we can update the value of $$$dp$$$ for $$$k + 1, k + 1 + 2, \ldots$$$ — a total of $$$O(\sqrt{s})$$$ values not exceeding $$$s$$$. In this same $$$dp$$$, we can store through which values we were recalculated, for the restoration of the answer.
Now, we can iterate over the length of the first block of the form $$$b_1, b_1 + 1, \ldots, b_1 + k_1$$$. Then we know the sum of the remaining blocks, and using the precalculated $$$dp$$$, we can determine whether the desired sequence can be formed or not.