Til er strengjabreytingavél sem vinnur sérstaklega með $\texttt{01}$-strengi og hefur innbyggt endanlegt mengi reglna $\mathcal{R}$. Hver regla er á forminu $(u, v)$, þar sem $u, v$ eru ekki tómir $\texttt{01}$-strengir af sömu lengd, sem þýðir að í einu aðgerðarskrefi má velja hlutstreng $u$ í núverandi streng og skipta honum út fyrir $v$. Í hvert sinn sem par af ekki tómum $\texttt{01}$-strengjum af sömu lengd $(s, t)$ er sett inn í vélina skilar vélin lágmarksfjölda aðgerðarskrefa sem þarf til að breyta $s$ í $t$, eða tilkynnir að engin lausn sé til.

Þú manst eftir því að hafa einu sinni sett $n$ pör af ekki tómum $\texttt{01}$-strengjum af sömu lengd $(s_1, t_1), (s_2, t_2), \dots, (s_n, t_n)$ inn í þessa vél. Fyrir tilviljun hafði sérhver fyrirspurn í minningunni ekki aðeins lausn heldur uppfyllti einnig að lágmarksfjöldi aðgerðarskrefa var $d_i \leqslant 2$.

Til að kanna hvort minnið sé að svíkja þig skaltu ákvarða: er til reglumengi $\mathcal{R}$ þannig að raunveruleg úttök vélarinnar fyrir þessi $n$ inntök séu í fullu samræmi við minningu þína?

Inntak

Fyrsta línan inniheldur jákvæða heiltölu $T$, sem táknar fjölda prófunartilvika.

Fyrir hvert prófunartilvik inniheldur fyrsta línan jákvæða heiltölu $n$, sem táknar fjölda fyrirspurnarfærslna. Í næstu $n$ línum inniheldur $i$-ta línan tvo ekki tóma $\texttt{01}$-strengi af sömu lengd $s_i, t_i$ og heiltölu $d_i$ ($0 \leqslant d_i \leqslant 2$), sem tákna upphafsstrenginn, markstrenginn og lágmarksfjölda aðgerðarskrefa sem vélin gaf upp fyrir $i$-ta inntakið.

Úttak

Fyrir hvert prófunartilvik skal prenta eina línu með einum streng. Ef til er reglumengi $\mathcal{R}$ sem uppfyllir skilyrðin skal prenta YES; annars skal prenta NO.

Þú mátt prenta YES og NO með hvaða samsetningu há- og lágstafa sem er; til dæmis teljast yes, Yes og YES öll sama svarið.

Dæmi

Inntak 1

3
3
010 010 0
001 010 1
001 100 2
2
10 01 1
100 010 2
1
0 1 2

Úttak 1

YES
NO
NO

Skýring

• Prófunartilvik $1$: Hægt er að smíða mengi sem inniheldur aðeins eina reglu, $\mathcal{R} = \{(\texttt{01}, \texttt{10})\}$:
  • Fyrir $1$. fyrirspurnina gildir $s_1 = t_1 = \texttt{010}$, þannig að breytingin klárast án nokkurra aðgerða og lágmarksfjöldi aðgerðarskrefa er $0$.
  • Fyrir $2$. fyrirspurnina má skipta viðskeytinu $\texttt{01}$ í $\texttt{001}$ út fyrir $\texttt{10}$ og fá þannig $\texttt{010}$ í $1$ skrefi.
  • Fyrir $3$. fyrirspurnina, þar sem $\texttt{001}$ og $\texttt{100}$ eru ólíkir bæði í $1$. og $3$. sæti, getur regla af lengd $2$ ein og sér ekki klárað breytinguna í $1$ skrefi; hins vegar má fyrst skipta viðskeytinu $\texttt{01}$ í upphafsstrengnum $\texttt{001}$ út fyrir $\texttt{10}$ til að fá millistrenginn $\texttt{010}$, og síðan skipta forskeytinu $\texttt{01}$ í millistrengnum $\texttt{010}$ út fyrir $\texttt{10}$ til að fá markstrenginn $\texttt{100}$, svo lágmarksfjöldi aðgerðarskrefa er $2$.
• Prófunartilvik $2$: Til að breyta $\texttt{10}$ í $\texttt{01}$ í $1$ skrefi verður reglumengið $\mathcal{R}$ að innihalda regluna $(\texttt{10}, \texttt{01})$. En um leið og sú regla er tekin með þarf í $2$. fyrirspurninni aðeins að skipta forskeytinu $\texttt{10}$ í $\texttt{100}$ út fyrir $\texttt{01}$ til að fá $\texttt{010}$ í $1$ skrefi, sem stangast á við $d_2 = 2$ í minningu þinni.
• Prófunartilvik $3$: Allir strengir í breytingaferlinu verða að vera $\texttt{01}$-strengir af sömu lengd. Það eru aðeins tveir $\texttt{01}$-strengir af lengd $1$, nefnilega $\texttt{0}$ og $\texttt{1}$. Ef hægt er að breyta $\texttt{0}$ í $\texttt{1}$ hlýtur reglan $(\texttt{0}, \texttt{1})$ að vera til og þá dugar $1$ skref til að ljúka verkinu, svo ómögulegt er að það þurfi að minnsta kosti $2$ skref.

Takmarkanir

Fyrir öll prófunargögn er tryggt að $T \geqslant 1$, $n \geqslant 1$, $0 \leqslant d_i \leqslant 2$, $1 \leqslant |s_i| = |t_i|$, og að bæði $s_i, t_i$ séu strengir sem samanstanda eingöngu af stöfunum $\texttt{0}$ og $\texttt{1}$.

Látum $L = \sum_{i=1}^{n} |s_i|$ vera summu lengda allra upphafsstrengja í einu prófunartilviki og $\sum L$ vera summu $L$ yfir öll prófunartilvik í einni prófunarskrá; tryggt er að $\sum L \leqslant 3\times 10^6$.

Í þessu dæmi eru eðlilegar tengsl milli undirliða virkjuð.

• Sérstakur eiginleiki A: Tryggt er að fyrir öll $1 \leqslant i \leqslant n$ gildi $|s_i| \geqslant 50$.