Egy játékban varázslók lehetünk és elemeket idézhetünk meg. Nyolc alapvető elem létezik, ezeket a következő karakterek jelölik:
{Q,W,E,R,A,S,D,F}. Amikor megidézünk egy elemet, az felkerül az elemeinket tartalmazó lista végére. Például ha először az A, majd utána a W elemet idézzük meg, akkor listánk így néz ki: [A,W].

Bizonyos alapvető elemek össze tudnak kombinálódni, és így új elemek keletkezhetnek. Ezek az új elemek különböznek az alapvető elemektől, és az angol ábécé további 18 betűjével jelöljük őket. Például egy Q és egy F összekombinálódhat és így létrejöhet például egy T. Ez csak akkor következik be, ha a két kombinálódásra képes elem a lista végén, egymás mellett jelent meg. Ilyenkor rögtön törlődnek a listáról, és az általuk létrehozott új elem kerül a helyükre, a lista végén. Az előző példát folytatva, ha az elemek listája [A,Q,F] vagy [A,F,Q], akkor rögtön átalakul, és [A,T] lesz belőle.

Vannak olyan alapvető elemek is, amelyek ellentétesek. Ha egy elemet megidéztünk, és nem kombinálódott össze új elemmé, de a lista valamelyik korábbi elemével ellentétes, akkor a teljes lista törlődik. Például ha Q és F T-vé kombinálódik, továbbá R és F ellentétes, akkor a következők történhetnek:

• QF → [T] (Q és F összekombinálódik T-vé)
• QEF → [Q, E, F] (Q és F nem szomszédos, nem kombinálódnak)
• RFE → [E] (F és R ellentétes, a lista törlődik, majd E-t idéztük meg)
• REF → [] (F és  R ellentétes, a lista törlődik)
• RQF → [R, T] (QF átalakul T-vé, ezért a lista nem törlődik)
• RFQ → [Q] (F és  R ellentétes, a lista törlődik, ...)

Írjunk programot, ami a megidézett elemek ismeretében megadja, hogy végül mi maradt az elem-listában!

A bemenet első sora a tesztesetek T számát adja meg (1 ≤ T ≤ 100), ezután T sorban egy-egy teszteset következik. Minden teszteset egyetlen, szóközökkel tagolt sor, ami a következő módon épül fel:

• Először egy C egész áll (0 ≤ C ≤ 36), majd C karakterlánc, mindegyik 3 betűt tartalmaz, a két alapvető elem, és a belőlük kombinálódó harmadik elem betűjelét.
• Ezután egy D egész jön (0 ≤ D ≤ 28), majd D darab kétbetűs karakterlánc, az ellentétes elemek párjai.
• Végül egy N egész következik (1 ≤ N ≤ 100), és utána egy N karakter hosszú karakterlánc, a megidézett elemek sorozata.

Minden tesztesethez írjuk ki a végül megmaradó elem-listát, a példának megfelelő formátumban.

Bemenet	Kimenet
5 0 0 2 EA 1 QRI 0 4 RRQR 1 QFT 1 QF 7 FAQFDFQ 1 EEZ 1 QE 7 QEEEERA 0 1 QW 2 QW	Case #1: [E, A] Case #2: [R, I, R] Case #3: [F, D, T] Case #4: [Z, E, R, A] Case #5: []

m1.in m1.out m2.in m2.out

A feladat forrása: Google Code Jam 2011 Qualification Round (link)

Algoritmusok: listakezelés, karakterláncok lexikális elemzése