Tässä tehtävässä on liitetiedosto. Voit käyttää sitä robotin liikkeiden simulointiin ja visualisointiin.

VegiCatilla on robotti äärettömässä kaksiulotteisessa ruudukossa. Hän haluaa sen siirtyvän ruudusta $s = (s_x, s_y)$ ruutuun $t = (t_x, t_y)$. Jokaisella ruudulla on kokonaislukukoordinaatit. Ruudut $s$ ja $t$ voivat olla samat.

Robotti noudattaa ohjemerkkijonoa $p$. Jokainen merkki on L, R, U tai D. Merkitään merkkijonon $p$ pituutta $|p|$.

Robotti aloittaa ruudusta $s$. Ennen kuin se suorittaa yhtäkään ohjetta, voit asettaa enintään $|p|$ estettä eri ruutuihin. Jokaisen esteen koordinaattien $(x, y)$ on toteutettava ehto $-2 \cdot 10^9 \le x, y \le 2 \cdot 10^9$. Ruuduissa $s$ ja $t$ ei saa olla estettä. Jokainen este vie yhden ruudun ja pysyy paikallaan koko prosessin ajan; kaikki muut ruudut ovat esteettömiä.

Robotti suorittaa ohjeet $p_1, p_2, \ldots, p_{|p|}$ järjestyksessä. Jokaisella ohjeella se liikkuu nykyisestä ruudustaan $(x, y)$ lähtien seuraavan ruutujonon mukaisesti:

• L: $(x, y) \to (x - 1, y) \to (x - 2, y) \to \cdots$;
• R: $(x, y) \to (x + 1, y) \to (x + 2, y) \to \cdots$;
• U: $(x, y) \to (x, y + 1) \to (x, y + 2) \to \cdots$;
• D: $(x, y) \to (x, y - 1) \to (x, y - 2) \to \cdots$.

Robotti ottaa toistuvasti yhden askeleen määrättyyn suuntaan niin kauan kuin seuraavassa ruudussa ei ole estettä. Se pysähtyy ruutuun, joka on välittömästi ennen kyseisen suunnan ensimmäistä estettä. Jos määrätyn suunnan seuraavassa ruudussa on este jo ennen ohjeen alkamista, robotti pysyy paikallaan, mutta ohje katsotaan silti suoritetuksi. Jos kyseisessä suunnassa ei ole edessä yhtäkään estettä, robotti liikkuisi ikuisesti, ja sijoittelu on virheellinen.

Robotti voi saavuttaa ruudun $t$ ennen kuin kaikki ohjeet on suoritettu. Sen on silti suoritettava kaikki jäljellä olevat ohjeet. Muodosta mikä tahansa yllä olevat vaatimukset täyttävä esteiden sijoittelu, jolla robotti päätyy ruutuun $t$ viimeisen ohjeen jälkeen, tai ilmoita, ettei sellaista sijoittelua ole olemassa.

Syöte

Ensimmäisellä rivillä on kokonaisluku $T$ ($1 \le T \le 10^5$), testitapausten lukumäärä. Seuraavaksi annetaan testitapausten kuvaukset.

Jokaisen testitapauksen ensimmäisellä rivillä on kaksi kokonaislukua $s_x$ ja $s_y$ ($-10^9 \le s_x, s_y \le 10^9$), aloitusruudun koordinaatit.

Toisella rivillä on kaksi kokonaislukua $t_x$ ja $t_y$ ($-10^9 \le t_x, t_y \le 10^9$), kohderuudun koordinaatit.

Kolmannella rivillä on ohjemerkkijono $p$ ($1 \le |p| \le 10^5$), joka koostuu vain merkeistä L, R, U ja D.

On taattu, että lukujen $|p|$ summa yli kaikkien testitapausten on enintään $10^5$.

Tuloste

Tulosta jokaiselle testitapaukselle vastaus syötejärjestyksessä. Eri testitapausten estesijoittelut ovat toisistaan riippumattomia.

Jos kelvollista sijoittelua ei ole olemassa, tulosta NO omalle rivilleen.

Muussa tapauksessa tulosta ensimmäiselle riville YES. Tulosta toiselle riville kokonaisluku $k$ ($0 \le k \le |p|$), esteiden lukumäärä.

Tulosta sen jälkeen $k$ riviä. Näistä $i$:nnellä rivillä on oltava kaksi kokonaislukua $x_i$ ja $y_i$ ($-2 \cdot 10^9 \le x_i, y_i \le 2 \cdot 10^9$), jotka määrittävät esteen ruutuun $(x_i, y_i)$.

Kaikkien $k$ koordinaattiparin on oltava keskenään erilaisia, eikä mikään niistä saa olla $s$ tai $t$. Sijoittelun on mahdollistettava jokaisen ohjeen päättyminen ja jätettävä robotti ruutuun $t$ viimeisen ohjeen jälkeen. Jos ratkaisuja on useita, tulosta mikä tahansa niistä.

Voit tulostaa yes- tai no-vastauksen millä tahansa kirjainkoolla. Esimerkiksi yEs, yes, Yes ja YES hyväksytään kaikki myöntäviksi vastauksiksi.

Esimerkit

Syöte 1

6
0 0
1 0
RL
0 0
-1 0
URD
0 0
8 0
RLR
0 0
0 0
UDUD
0 0
2 5
RDULR
0 0
1 1
RURURU

Tuloste 1

NO
NO
YES
2
-1 0
9 0
YES
2
0 -1
0 1
YES
5
-1 5
2 -1
2 6
3 0
3 5
YES
3
1 2
2 0
2 1