Descripción
El problema constructivo más aburrido del mundo consiste en leer $n, m$ e imprimir una matriz que cumpla las condiciones 1, 2, 3, 4, 5, 6, 7, 8.
Dados cuatro enteros $a, b, n, s$ ($a \neq b$). Necesitas construir una secuencia $c$ de longitud $n$ tal que:
- Para todo $1 \le i \le n$, $c_i \in \{a, b\}$;
- No exista ningún subarreglo contiguo $c_l, c_{l+1}, \dots, c_r$ cuya suma sea exactamente $s$.
Más formalmente, no existen enteros $(l, r)$ que cumplan $1 \le l \le r \le n$ tales que $c_l + c_{l+1} + \dots + c_r = s$.
Para cada caso de prueba, determina si existe tal secuencia:
- Si existe, imprime
YESe imprime cualquier secuencia válida; - En caso contrario, imprime
NO.
Entrada
La primera línea contiene un entero $T$ ($1 \le T \le 10^5$), que denota el número de casos de prueba.
Cada una de las siguientes $T$ líneas contiene cuatro enteros $a, b, n, s$ ($1 \le a, b, s \le 10^9$, $1 \le n \le 5 \cdot 10^5$, $a \neq b$).
Se garantiza que la suma de todos los $n$ no supera $5 \cdot 10^5$.
Salida
Para cada caso de prueba:
- Si no hay solución, imprime una línea que contenga
NO; - Si hay solución, primero imprime una línea que contenga
YES, y luego imprime una línea con $n$ enteros que representen la secuencia que construiste.
Si hay múltiples respuestas válidas, imprime cualquiera de ellas.
Ejemplos
Entrada 1
3 2 4 6 8 2 5 5 9 3 4 3 7
Salida 1
NO YES 2 5 5 5 2 YES 4 4 4