Problem C
Tunnelbaneträngsel

Lovisa bor inte i Stockholm och är ganska ovan vid att åka tunnelbana. En dag som i dag när det är hela $N$ personer på tåget och det inte finns några sittplatser kvar vill hon gärna hålla i sig i något för att inte trilla. Dessvärre har hon hamnat mitt bland en massa människor och når inte till något handtag på väggen. Hennes lösning på det är att istället ta tag i ryggsäckshandtaget på någon av personerna som står närmast. För att det ska fungera gäller det dock att den personen håller fast sig i något; annars kommer ju båda trilla när Lovisa trillar.

En del personer håller fast sig i vägghandtag och kommer aldrig trilla. Utöver det finns det tydligen andra i folkmassan som har samma strategi som Lovisa och håller i sig i ryggsäckshandtagen på dem runt omkring. I allmänhet gäller det att en person inte kommer trilla antingen om hen håller i någon som inte trillar eller om någon som inte trillar håller i hen. I praktiken innebär det att för att man inte ska trilla måste det finnas en kedja av människor fram till ett vägghandtag. Alla personer håller fast i noll, en eller två saker, där saker kan vara både vägghandtag och ryggsäckshandtag.

Nu vill Lovisa veta vem av personerna som står närmast hon ska ta tag i för att inte trilla. Om det finns flera personer vill hon ta tag i en person som står så nära väggen som möjligt, det vill säga att det är en så kort kedja av människor som möjligt mellan personen och den närmaste väggen.

Indata

Den första raden indata består av de två heltalen $N$ och $A$ ($1 \leq N \leq 10^5, 1 \leq A \leq N$), antalet personer på tunnelbanan (Lovisa räknas inte) och antalet personer som står nära Lovisa.

Efter det kommer en rad med $A$ strängar, namnen på personerna som står närmast Lovisa.

Därefter följer $N$ rader bestående av tre ord. Varje rad beskriver vad en person i tunnelbanan håller i; det första ordet är namnet på personen och de andra två är vad personen håller i vardera handen. Om personen håller i ett vägghandtag står det ”wall” och om personen inte håller i något står det ”nothing”, annars står det namnet på ägaren till ryggsäckshandtaget som personen håller i. Person $i$ och $j$ har olika namn för alla $i \neq j$ , och det finns ingen i tunnelbanan förutom person $1-N$ och Lovisa.

Det är garanterat att alla namn är strängar som är mindre än $20$ tecken och att alla tecken är små bokstäver som förekommer i det engelska alfabetet. Dessutom heter inga två personer samma sak, bara Lovisa heter ”lovisa” och ingen alls heter ”wall” eller ”nothing”.

Utdata

Skriv ut ett namn, personen som Lovisa ska ta tag i. Om det finns flera som som står lika nära väggen kan du skriva ut vilken som helst av dem. Om det inte finns någon Lovisa kan ta tag i för att inte trilla ska du skriva ut ”aj!”.

Poängsättning

Din lösning kommer att testas på flera olika testgrupper. För att få poäng för en grupp så måste du klara alla testfall i gruppen. Ifall du skriver ut namnet på en person som skulle hindra Lovisa från att ramla, men står längre ifrån väggen än någon annan i närheten, får du halvt rätt på testfallet. (Detta räknas fortfarande som att du har klarat fallet.) Om du får halvt rätt på något testfall i en testgrupp och helt rätt på alla andra testfall i gruppen får du 50% av poängen för testgruppen.

Förklaring

I det första exempelfallet är det bara Simons ryggsäck Lovisa kan ta tag i för att inte trilla. Eftersom han inte håller i något kommer båda trilla när Lovisa trillar och svaret är ”aj!”.

I det andra exempelfallet kan Lovisa ta tag i antingen Simons, Ruths eller Harrys ryggsäck. Ruth håller i väggen direkt och Harry håller i hennes ryggsäck, så båda deras ryggsäckar går bra att ta tag i. Ruth är dock bättre att ta tag i eftersom hon är närmare väggen (ingen person mellan istället för en), så för att få full poäng på testgruppen måste hennes namn skrivas ut. Om du skriver ut Harrys namn istället får du hälften av poängen för testgruppen.

I det tredje exempelfallet kan Lovisa ta tag i Ruths eller Simons ryggsäck. Eftersom Harry både håller i väggen och i Ruths ryggsäck står Ruth stabilt och kommer inte trilla. Därför kan Lovisa ta tag i Ruths ryggsäck för att inte trilla.

Figure 1: Personerna på tunnelbanan i exempelfall $3$.

2 1
simon
ruth wall nothing
simon nothing nothing

aj!

4 3
simon ruth harry
simon nothing nothing
ruth wall nothing
anita wall ruth
harry ruth nothing

ruth

4 2
simon ruth
simon nothing nothing
ruth anita nothing
anita harry ruth
harry ruth wall

ruth