Ohjelmointikieli

• Time limit: 6.00 s
• Memory limit: 128 MB

Uolevi on kehittänyt uuden erikoisen ohjelmointikielen. Siinä muistissa on joukko merkkijonoja, ja kielessä on vain yksi komento. Tehtäväsi on simuloida Uolevin kielellä tehdyn ohjelman suoritusta.

Syöte

Ensimmäisellä rivillä on luvut $n$, merkkijonojen määrä alussa, ja $q$, komentojen määrä.

Seuraavat $n$ riviä sisältävät joukossa valmiina olevat merkkijonot. Jokainen merkkijono on 8 merkin pituinen ja muodostuu merkeistä A–Z.

Seuraavat $q$ riviä sisältävät komennot. Jokaisessa komennossa on kaksi lukua $a$ ja $b$. Komento tarkoittaa, että joukosta valitaan aakkosjärjestyksessä $a$. ja $b$. merkkijono ja joukkoon lisätään uutena merkkijonona näiden merkkijonojen summa. Voit olettaa, että uusi merkkijono ei ole vielä joukossa.

Merkkijonojen summassa jokaiseen kohtaan uutta merkkijonoa tulee vastaavassa kohdissa olevien merkkien summa. Summassa merkit A–Z tulkitaan luvuiksi 0–25 ja uusi merkki on lukujen summa modulo 26. Esimerkiksi N + X = K, koska N ja X vastaavat lukuja 13 ja 23 ja K vastaa lukua 10 (13 + 23 modulo 26).

Tuloste

Ohjelmasi tulee tulostaa jokaisen komennon tuottama uusi merkkijono.

Rajat

• $1\leq n\leq 1000$
  
• $1\leq q\leq 10000$
  

Tehtävän aikaraja on poikkeuksellisesti 6 sekuntia.

Esimerkki

Syöte:
2 3
ABABABAB
BBBBBBBB
1 1
2 3
1 4

Tuloste:
ACACACAC
BDBDBDBD
BEBEBEBE