311061: CF1928E. Modular Sequence

E. Modular Sequencetime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

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

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

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.

ExampleInput

3
5 8 3 28
3 5 3 6
9 1 5 79

Output

YES
8 11 2 2 5 
NO
NO

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.

题目大意：
题目描述了一个“模序列”，它是由两个整数x和y定义的长度为n的序列a。如果a_1=x，并且对于所有1 < i ≤ n，a_i的值要么是a_{i-1} + y，要么是a_{i-1} mod y，则称序列a为模序列。需要判断是否存在一个长度为n的模序列，其元素之和等于S，如果存在，则找出这样的序列。

输入数据格式：
每个测试包含多个测试案例。第一行包含测试案例的数量t（1 ≤ t ≤ 2 * 10^4）。接下来是每个测试案例的描述。
每个测试案例的第一行包含四个整数n、x、y和s（1 ≤ n ≤ 2 * 10^5，0 ≤ x ≤ 2 * 10^5，1 ≤ y ≤ 2 * 10^5，0 ≤ s ≤ 2 * 10^5）——序列的长度和参数x、y以及序列元素所需的总和。
所有测试案例中n的总和不超过2 * 10^5，s的总和也不超过2 * 10^5。

输出数据格式：
对于每个测试案例，如果存在所需的序列，则在第一行输出"Yes"（不包含引号）。然后在第二行输出n个整数a_1, a_2, …, a_n，由空格分隔，代表序列a的元素。如果有多个合适的序列，输出其中任意一个。
如果序列不存在，则在单独的一行上输出"No"。
输出每个字母时大小写不限，例如，"yEs"、"yes"、"Yes"和"YES"都将被接受为肯定答案。题目大意： 题目描述了一个“模序列”，它是由两个整数x和y定义的长度为n的序列a。如果a_1=x，并且对于所有1 < i ≤ n，a_i的值要么是a_{i-1} + y，要么是a_{i-1} mod y，则称序列a为模序列。需要判断是否存在一个长度为n的模序列，其元素之和等于S，如果存在，则找出这样的序列。 输入数据格式： 每个测试包含多个测试案例。第一行包含测试案例的数量t（1 ≤ t ≤ 2 * 10^4）。接下来是每个测试案例的描述。 每个测试案例的第一行包含四个整数n、x、y和s（1 ≤ n ≤ 2 * 10^5，0 ≤ x ≤ 2 * 10^5，1 ≤ y ≤ 2 * 10^5，0 ≤ s ≤ 2 * 10^5）——序列的长度和参数x、y以及序列元素所需的总和。 所有测试案例中n的总和不超过2 * 10^5，s的总和也不超过2 * 10^5。 输出数据格式： 对于每个测试案例，如果存在所需的序列，则在第一行输出"Yes"（不包含引号）。然后在第二行输出n个整数a_1, a_2, …, a_n，由空格分隔，代表序列a的元素。如果有多个合适的序列，输出其中任意一个。 如果序列不存在，则在单独的一行上输出"No"。 输出每个字母时大小写不限，例如，"yEs"、"yes"、"Yes"和"YES"都将被接受为肯定答案。