Description

The most boring constructive problem in the world is to read $n, m$ and output a matrix satisfying conditions 1, 2, 3, 4, 5, 6, 7, 8.

Given four integers $a, b, n, s$ ($a \neq b$). You need to construct a sequence $c$ of length $n$ such that:

• For every $1 \le i \le n$, $c_i \in \{a, b\}$;
• There does not exist a contiguous subarray $c_l, c_{l+1}, \dots, c_r$ whose sum is exactly $s$.

More formally, there do not exist integers $(l, r)$ satisfying $1 \le l \le r \le n$ such that $c_l + c_{l+1} + \dots + c_r = s$.

For each test case, determine whether such a sequence exists:

• If it exists, output YES, and output any valid sequence;
• Otherwise, output NO.

Input

The first line contains an integer $T$ ($1 \le T \le 10^5$), denoting the number of test cases.

Each of the next $T$ lines contains four integers $a, b, n, s$ ($1 \le a, b, s \le 10^9$, $1 \le n \le 5 \cdot 10^5$, $a \neq b$).

It is guaranteed that the sum of all $n$ does not exceed $5 \cdot 10^5$.

Output

For each test case:

• If there is no solution, output a line containing NO;
• If there is a solution, first output a line containing YES, then output a line containing $n$ integers representing the sequence you constructed.

If there are multiple valid answers, output any of them.

Examples

input1

3
2 4 6 8
2 5 5 9
3 4 3 7

output1

NO
YES
2 5 5 5 2
YES
4 4 4