28384번 - Bliskost 서브태스크다국어

Jednom u proljeće, u vrijeme neobično topla sutona, pojavila su se na Patrijaršijskim ribnjacima u M*skvi dvojica građana. Prvi nije bio nitko drugi nego urednik Mihali Aleksandrovič Berlioz, dok je drugi bio mladi pjesnik zvan Bezdomni. Svaki je sa sobom imao svoj niz slova duljine $N$...

Ubrzo im se priključio tajnoviti specijalist za crnu magiju, profesor Woland, te rekao.

- Gospodo, imate vrlo zanimljijve nizove slova, te ja odmah naoko mogu odrediti jesu li oni bliski ili ne!

Jednim potezom smatra se odabiranja dvaju uzastopnih slova jednog niza, te pomicanjem obaju slova ciklički prema naprijed u abecedi, primjerice pretvarajući par slova “ab“ u par slova “bc“ tj. par slova “qz“ u par slova “ra“. Dva niza znakova smatraju se bliskima ako primjenjivanjem poteza na oba niza moguće je postići da su oni jednaki.

- Dakako, profesore, pričate gluposti. Problem određivanja bliskosti dvaju nizova notorno je težak.

- A ne, varate se Mihaile Aleksandroviču, i ja ću vam to upravo dokazati! Evo ovako, sada ću vam reći jesu li vaši nizovi bliski ili ne, te vi potom učinite $Q$ promjena na svojem nizu. Ja ću vam nakon svake promjene odrediti istinitost bliskosti vaših nizova.

- Veoma hrabro profesore, uistinu, veoma hrabro... pa započnimo!

U prvom su retku prirodni brojevi $N$ i $Q$, redom duljina nizova i broj promjena.

U drugom retku nalazi se niz znakova duljine $N$, niz koji pripada Berliozu.

U trećem retku nalazi se niz znakova duljine $N$, niz koji pripada Bezdomnom.

U $i$-tom od sljedećih $Q$ redaka nalazi se broj $p_i$ te znak $c_i$, koji označava da je u $i$-toj promjeni Berlioz promijenio $p_i$-to slovo u $c_i$.

U prvi redak potrebno je ispisati “da“ ako su početni nizovi bliski, odnosno “ne“ ako nisu.

U i-tom od sljedećih $Q$ redaka potrebno je ispisati jesu li nizovi bliski nakon $i$-te promjene Berlioza.

U prvom primjeru, nakon promjene, riječi su bliske sljedećim potezima:

abc → bcc → cdc → dec → dfd

ced → dfd