Zadanie

Lstivá kocka

Počet bodov: 90

Miško sa hrá s rubikovou kockou, najlepšou hračkou ľudstva! Obracia strany, skladá rôzne vzory. Už urobil \(n\) ťahov, keď ho zastaví Jožko, ktorý je v skladaní rubikovej kocky značne skúsenejší. “V treťom ťahu si mal otočiť zadnú stenu v smere hodinových ručičiek.” “V stoštyridsiatom-piatom ťahu si mal radšej otočiť vrchnú stenu proti smeru hodinových ručičiek.” A tak ďalej, celkovo mu Jožko dá \(m\) takýchto rád.

Miško je skeptický a najprv by rád vedel aký efekt budú mať navrhované zmeny. Pomôžte Miškovi zistiť, ako bude kocka vyzerať po uplatnení Jožkovich rád.

Úloha

Dostanete rubikovu kocku, postupnosť ťahov a postupnosť zmien týchto ťahov. Po každej zmene vypíšte, ako vyzerá výsledná kocka.

Formát kocky

Farby kocky označme \(A\),\(B\),\(C\),\(D\),\(E\),\(F\). Keď sa hráte s kockou nemení sa vzájomná poloha stredných štvorčekov. Teda vieme kocku vždy zrotovať tak, aby stredné štvorčeky mali fixné pozície. Potom môžeme rozbaliť povrch kocky a získame jednoznačný popis kocky:

???
?A?
???
????????????
?B??C??D??E?
????????????
???
?F?
???

Vstup a Výstup

Prvých 9 riadkov vstupu tvorí popis počiatočného stavu kocky. Nasleduje riadok s dvoma číslami; \(n\), počet ťahov ktoré Miško urobí, a \(m\), počet zmien. Platí \(n,m \leq 65000\).

Nasleduje \(n\) riadkov popisujúcich jednotlivé ťahy. Majú tvar \(C_i\) \(d_i\), pričom \(C_i\) je stred strany kocky ktorou točíme a \(d_i\) je \(-1\) ak točíme v smere a \(1\) ak točíme proti smeru hodinových ručičiek.

Posledných \(m\) riadkov popisuje zmeny. Majú tvar \(a_j\) \(C_j\) \(d_j\), kde \(a_j\) je číslo ťahu, ktorý sa nahradzuje a \(C_j\) \(d_j\) popisujú nový ťah. Ťahy sú číslované \(1\) až \(n\).

Pre každú zmenu vypíšte na výstup 9 riadkov popisujúcich konečný stav kocky po tejto zmene.

Vstupy

V prvých piatich vstupoch \(m,n \le 10\).

V ďaľších piatich vstupoch \(m,n \le 1000\).

V ďaľších piatich vstupoch \(m \le 10000\), \(n \le 5000\).

V ďaľších piatich vstupoch \(m,n \le 65000\).

Príklad

Input:

AAA
AAA
AAA
BBBCCCDDDEEE
BBBCCCDDDEEE
BBBCCCDDDEEE
FFF
FFF
FFF
8 4
E 1
E -1
F 1
F -1
B 1
B -1
E 1
E -1
8 C -1
2 C -1
6 D -1
4 A -1

Output:

BAB
BAB
BAB
FBFCCCADAEEE
FBFCCCADAEEE
FBFCCCADAEEE
DFD
DFD
DFD
FAF
FAF
FAF
DBDCCCBDBEEE
DBDCCCBDBEEE
DBDCCCBDBEEE
AFA
AFA
AFA
FCF
BAB
FCF
EFEDFDCACBAB
DBDCCCBDBEEE
EFEDFDCACBAB
AEA
DFD
AEA
CCC
CAC
CCC
FFFDDDAAABBB
FBFDCDADABEB
FFFDDDAAABBB
EEE
EFE
EEE

Pôvodné ťahy sa navzájom vyrušia. Postupne ich meníme na známy trik rotácie stredov.