Opis problemu
Najbardziej nudnym zadaniem konstrukcyjnym na świecie jest wczytanie $n, m$ i wypisanie macierzy spełniającej warunki 1, 2, 3, 4, 5, 6, 7, 8.
Dane są cztery liczby całkowite $a, b, n, s$ ($a \neq b$). Musisz skonstruować ciąg $c$ o długości $n$ taki, że:
- Dla każdego $1 \le i \le n$ zachodzi $c_i \in \{a, b\}$;
- Nie istnieje spójny podciąg $c_l, c_{l+1}, \dots, c_r$, którego suma wynosi dokładnie $s$.
Bardziej formalnie, nie istnieją liczby całkowite $(l, r)$ spełniające $1 \le l \le r \le n$ takie, że $c_l + c_{l+1} + \dots + c_r = s$.
Dla każdego przypadku testowego rozstrzygnij, czy taki ciąg istnieje:
- Jeśli istnieje, wypisz
YESoraz dowolny poprawny ciąg; - W przeciwnym razie wypisz
NO.
Wejście
Pierwszy wiersz zawiera liczbę całkowitą $T$ ($1 \le T \le 10^5$), oznaczającą liczbę przypadków testowych.
Każdy z kolejnych $T$ wierszy zawiera cztery liczby całkowite $a, b, n, s$ ($1 \le a, b, s \le 10^9$, $1 \le n \le 5 \cdot 10^5$, $a \neq b$).
Gwarantowane jest, że suma wszystkich $n$ nie przekracza $5 \cdot 10^5$.
Wyjście
Dla każdego przypadku testowego:
- Jeśli nie ma rozwiązania, wypisz wiersz zawierający
NO; - Jeśli rozwiązanie istnieje, najpierw wypisz wiersz zawierający
YES, a następnie wiersz zawierający $n$ liczb całkowitych reprezentujących skonstruowany ciąg.
Jeśli istnieje wiele poprawnych odpowiedzi, wypisz dowolną z nich.
Przykłady
Wejście 1
3 2 4 6 8 2 5 5 9 3 4 3 7
Wyjście 1
NO YES 2 5 5 5 2 YES 4 4 4