Descrizione

Il problema costruttivo più noioso del mondo consiste nel leggere $n, m$ e stampare una matrice che soddisfi le condizioni 1, 2, 3, 4, 5, 6, 7, 8.

Dati quattro interi $a, b, n, s$ ($a \neq b$). Devi costruire una sequenza $c$ di lunghezza $n$ tale che:

• Per ogni $1 \le i \le n$, $c_i \in \{a, b\}$;
• Non esista alcun sottoarray contiguo $c_l, c_{l+1}, \dots, c_r$ la cui somma sia esattamente $s$.

Più formalmente, non esistono interi $(l, r)$ che soddisfano $1 \le l \le r \le n$ tali che $c_l + c_{l+1} + \dots + c_r = s$.

Per ogni caso di test, determina se una tale sequenza esiste:

• Se esiste, stampa YES e stampa una qualsiasi sequenza valida;
• Altrimenti, stampa NO.

Input

La prima riga contiene un intero $T$ ($1 \le T \le 10^5$), che indica il numero di casi di test.

Ciascuna delle successive $T$ righe contiene quattro interi $a, b, n, s$ ($1 \le a, b, s \le 10^9$, $1 \le n \le 5 \cdot 10^5$, $a \neq b$).

È garantito che la somma di tutti gli $n$ non supera $5 \cdot 10^5$.

Output

Per ogni caso di test:

• Se non c'è soluzione, stampa una riga contenente NO;
• Se c'è una soluzione, stampa prima una riga contenente YES, poi stampa una riga contenente $n$ interi che rappresentano la sequenza che hai costruito.

Se ci sono più risposte valide, stampane una qualsiasi.

Esempi

Input 1

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

Output 1

NO
YES
2 5 5 5 2
YES
4 4 4