Murtoviiva

• Time limit: 1.00 s
• Memory limit: 512 MB

Murtoviiva koostuu $n$ vaakasuorasta janasta ja $n-1$ pystysuorasta janasta. Vaakasuorat janat on numeroitu järjestyksessä $1,2,\dots,n$, ja peräkkäisiä vaakasuoria janoja yhdistää yksi pystysuora jana. Ensimmäinen vaakasuora jana kulkee vasemmalta oikealle, ja sen jälkeen seuraavat vaakasuorat janat kulkevat vuorotellen vastakkaisiin suuntiin.

Tiedossa on vaakasuorien janojen pituudet sekä pystysuorien janojen suunnat, mutta ei pystysuorien janojen pituuksia. Voidaanko pystysuorien janojen pituudet valita niin, että murtoviiva ei leikkaa itseään?

Syöte

Ensimmäisellä rivillä on yksi kokonaisluku: vaakasuorien janojen määrä $n$.

Toisella rivillä on $n$ kokonaislukua $p_1, p_2, \ldots, p_n$: vaakasuorien janojen pituudet.

Viimeisellä rivillä on merkkijono, jossa on $n-1$ merkkiä. Jokainen merkki ilmaisee pystysuoran janan suunnan: U (ylöspäin) tai D (alaspäin).

Tuloste

Tulosta ensimmäiselle riville YES, jos ratkaisu on olemassa, ja muuten NO.

Jos ratkaisu on olemassa, tulosta seuraavalle riville $n-1$ positiivista kokonaislukua: pystysuorien janojen pituudet järjestyksessä. Pituudet eivät saa olla yli $10^9$.

Esimerkki

Syöte:
4
4 3 2 3
UDD

Tuloste:
YES
3 1 1

Selitys: Kuvaan on merkitty janojen suunnat ja pituudet.

Osatehtävä 1 (7 pistettä)

• $2 \le n \le 8$
  
• $1 \le p_i \le 10$
  

Osatehtävä 2 (19 pistettä)

• $2 \le n \le 15$
  
• $1 \le p_i \le 100$
  

Osatehtävä 3 (15 pistettä)

• $2 \le n \le 1000$
  
• $1 \le p_i \le 2$
  
• Murtoviiva mahtuu alueelle, jonka leveys on 2.
  

Osatehtävä 4 (33 pistettä)

• $2 \le n \le 1000$
  
• $1 \le p_i \le 10^6$
  

Osatehtävä 5 (26 pistettä)

• $2 \leq n \leq 10^5$
  
• $1 \leq p_i \leq 10^9$