Problem G
Cut in Line

You are currently standing in line, waiting to buy some algorithm books at the university book shop. Of course, the line is incredibly long. Even worse, some of your fellow university students keep cutting in line! In fact, this has been going on for such a long time you are unsure of your current position in the line.

Up until now, you have memorized how the line looked when you entered the line, what people have entered the line, and what people have left the line. Not only the first person in the line can leave – someone in the middle can leave if they grow tired of waiting.

Write a program where you can input the data of how the line changed, and output how the line currently looks.

Input

The first line of the input contains the integer $N$ ($1 \le N \le 1000$), the number of people currently in line. The next $N$ lines contains the names of the person initially in the line, from the first to the last.

The next line contains the integer $C$ ($0 \le C \le 1000$) – the number of people who entered or left the line.

The next $C$ lines contain the events, in the order that the events happened. If someone cut in line, the event will be cut a b, where a is the name of the person who cut in line, and b is the name of the person they stand in front of. If someone left the line, the event will be leave a, where a is the name of the person who left the line.

All names are single words of length at most $20$ containing only lower-case letters a-z. No two people will have the same name. Nobody will ever leave the queue and then enter it again.

Output

Output the names of everyone in the line after all the events in the order they stand from first to last, one name per line.

Explanation of sample 1

In the first example, the queue looks like this throughout the events:

• a b c d (initial)

• a e b c d (e cuts in front of b)

• a e b c (d leaves)

• e b c (a leaves)

• f e b c (f cuts in front of e).

4
a
b
c
d
4
cut e b
leave d
leave a
cut f e

f
e
b
c

5
alf
beata
cornelius
dagmar
eloise
5
leave eloise
cut fritiof cornelius
leave dagmar
cut germund alf
leave cornelius

germund
alf
beata
fritiof