Problem C
Subway Chaos

Lovisa doesn’t live in Stockholm and is not very familiar with riding the subway. On a day like today, when there are $N$ people on the train and no seats left, she’d like to hold onto something to avoid falling. Unfortunately, she’s stuck in the middle of a crowd and can’t reach any handles on the wall. Her solution is instead to grab onto the backpack handle of someone standing nearby. However, for this to work, that person must themselves be holding onto something; otherwise, both of them will fall when Lovisa does.

Some people hold onto wall handles and will never fall. Additionally, there seem to be others in the crowd with the same strategy as Lovisa, holding onto backpack handles of those around them. Generally, a person won’t fall either if they’re holding onto someone who won’t fall or if someone who won’t fall is holding onto them. Practically, this means that to avoid falling, there must be a chain of people connecting a person to a wall handle. Each person holds onto zero, one, or two items, where an item can be either a wall handle or another person’s backpack handle.

Lovisa now wants to know which of the people standing nearest to her she should grab onto to avoid falling. If multiple people can prevent her from falling, she prefers the one closest to the wall, meaning the shortest possible chain of people between that person and the nearest wall handle.

Input

The first line of input contains two integers $N$ and $A$ ($1 \leq N \leq 10^5, 1 \leq A \leq N$), the number of people on the subway (excluding Lovisa) and the number of people standing close to Lovisa.

The next line contains $A$ strings, the names of the people standing close to Lovisa.

Then follow $N$ lines, each consisting of three words. Each line describes what a person on the subway is holding onto; the first word is the person’s name, and the other two words describe what the person is holding in each hand. If the person is holding onto a wall handle, the word is “wall”. If the person is holding nothing, the word is “nothing”. Otherwise, the word is the name of the owner of the backpack handle that the person is holding onto. Each person $i$ and $j$ have distinct names for all $i \neq j$, and no one on the subway other than people $1-N$ and Lovisa exists.

It is guaranteed that all names are strings of fewer than $20$ characters, consisting only of lowercase letters from the English alphabet. Moreover, no two people have the same name, only Lovisa is named “lovisa”, and no one is named “wall” or “nothing”.

Output

Output one name, the person Lovisa should grab onto. If multiple people are equally close to the wall, you may output any of them. If there is no suitable person, print “aj!”.

Scoring

Your solution will be tested on several test groups. To receive points for a group, you must pass all test cases in the group. If you output the name of a person who prevents Lovisa from falling but is not the closest to the wall, you’ll get half credit on that test case. (This still counts as passing the case.) If you get half credit on any test case in a test group and full credit on all other cases in the group, you’ll receive 50% of the group’s points.

Explanation

In the first sample case, the only backpack Lovisa can grab is Simon’s. Since he’s not holding anything, they’ll both fall if Lovisa grabs his backpack, and the output is “aj!”.

In the second sample case, Lovisa can grab onto Simon’s, Ruth’s, or Harry’s backpack. Ruth directly holds the wall, and Harry holds onto Ruth’s backpack, so both are safe. However, Ruth is better because she’s closer to the wall (zero people between Ruth and the wall versus one for Harry), so to receive full points for the test group, you must output Ruth’s name. If you output Harry’s name instead, you receive half the points for the test group.

In the third sample case, Lovisa can grab onto Ruth’s or Simon’s backpack. Since Harry is holding both the wall and Ruth’s backpack, Ruth is stable and won’t fall. Thus, Lovisa can safely grab Ruth’s backpack to avoid falling.

Figure 1: The persons in the train car in sample $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