Tehtävänanto
Maailman tylsin konstruktiivinen tehtävä on lukea $n, m$ ja tulostaa matriisi, joka täyttää ehdot 1, 2, 3, 4, 5, 6, 7, 8.
Annettuna on neljä kokonaislukua $a, b, n, s$ ($a \neq b$). Sinun tulee muodostaa pituutta $n$ oleva lukujono $c$ siten, että:
- Jokaisella $1 \le i \le n$ pätee $c_i \in \{a, b\}$;
- Ei ole olemassa yhtenäistä osajonoa $c_l, c_{l+1}, \dots, c_r$, jonka summa on täsmälleen $s$.
Muodollisemmin ei ole olemassa kokonaislukuja $(l, r)$, joilla $1 \le l \le r \le n$ ja $c_l + c_{l+1} + \dots + c_r = s$.
Selvitä jokaista testitapausta kohden, onko tällaista lukujonoa olemassa:
- Jos se on olemassa, tulosta
YESja mikä tahansa kelvollinen lukujono; - Muussa tapauksessa tulosta
NO.
Syöte
Ensimmäinen rivi sisältää kokonaisluvun $T$ ($1 \le T \le 10^5$), joka ilmaisee testitapausten lukumäärän.
Jokainen seuraavista $T$ rivistä sisältää neljä kokonaislukua $a, b, n, s$ ($1 \le a, b, s \le 10^9$, $1 \le n \le 5 \cdot 10^5$, $a \neq b$).
On taattu, että kaikkien lukujen $n$ summa on enintään $5 \cdot 10^5$.
Tuloste
Jokaista testitapausta kohden:
- Jos ratkaisua ei ole, tulosta rivi, joka sisältää
NO; - Jos ratkaisu on olemassa, tulosta ensin rivi, joka sisältää
YES, ja tulosta sitten rivi, joka sisältää $n$ kokonaislukua, jotka esittävät muodostamaasi lukujonoa.
Jos kelvollisia vastauksia on useita, voit tulostaa minkä tahansa niistä.
Esimerkit
Syöte 1
3 2 4 6 8 2 5 5 9 3 4 3 7
Tuloste 1
NO YES 2 5 5 5 2 YES 4 4 4