Problem C
Conga Line

There’s currently a dance party being held in a nondescript location. The party is joined by $N$ couples. To liven up the party, the host, who is not dancing, has decided to perform a conga line. As such, the host asks all the couples to stand in one line.

At first, each couple will be standing next to each other in line. For example, let there be $2$ couples in the party, Amelia-Bubba and Ollie-Udin. Thus, the line from front to back will be Amelia, Bubba, Ollie, and Udin.

Then, the host will pass off a mic to the person at the front of the line, and will call out $Q$ instructions for the dancers to follow, consisting of these $5$ types:

1. $\texttt{F}$: The mic holder will pass the mic to the person in front of them. It is guaranteed that such a person exists.

2. $\texttt{B}$: The mic holder will pass the mic to the person behind them. It is guaranteed that such a person exists.

3. $\texttt{R}$: The mic holder will pass the mic to the person behind them. Then, they will move to the back of the line. In the case that the mic holder is at the back of the line, the mic will be passed to the person at the front of the line instead.

4. $\texttt{C}$: The mic holder will pass the mic to the person behind them. Then, they will move to behind where their partner is standing. In the case that the mic holder is at the back of the line, the mic will be passed to the person at the front of the line instead.

5. $\texttt{P}$: The mic holder will yell their partner’s name into the mic.

Note that the list of instructions will be given to you as a string of length $Q$ consisting of the $5$ characters written above.

The host has also invited you to the party as an event logger. Your task is to write down each name that is yelled during the conga line as well as the final conga line after all $Q$ instructions.

Input

The first line of input contains two integers $N$ ($1 \le N \le 250\, 000$) and $Q$ ($1 \le Q \le 1\, 000\, 000$), denoting the number of couples participating and the number of instructions respectively.

The next $N$ lines each contain two names, the names of a couple participating in the dance. The list of names will be given in accordance with the order they will be standing in the conga line. Each name will consist of at most $7$ lower-case Latin alphabet characters ($\texttt{'a'}$-$\texttt{'z'}$). It is guaranteed that the given names are unique.

The final line will be a string of length $Q$, representing the instructions given by the host. It is guaranteed that the string will only contain the characters $\texttt{F}$, $\texttt{B}$, $\texttt{R}$, $\texttt{C}$, and $\texttt{P}$.

Output

For each name yelled, print the name on a separate line in order. Then, print an empty line. Finally, print $2N$ lines, each containing the names of the person in the line from front to back.

Subtasks

1. ($15$ Points): There will be no $\texttt{P}$-type, $\texttt{R}$-type, or $\texttt{C}$-type instructions.

2. ($21$ Points): There will be no $\texttt{R}$-type or $\texttt{C}$-type instructions.

3. ($12$ Points): $N \le 100, Q \le 500$. There will be no $\texttt{C}$-type instructions.

4. ($12$ Points): $N \le 1\, 000, Q \le 3\, 000$. There will be no $\texttt{C}$-type instructions.

5. ($20$ Points): There will be no $\texttt{C}$-type instructions.

6. ($10$ Points): $N \le 1\, 000, Q \le 3\, 000$

7. ($10$ Points): No additional constraints.

Explanation

For the explanation below, all names will have their first character capitalized. However, all names in the input and output will be in lower-case.

In the first sample, the following illustration shows the line at the start of the game:

Then, the host calls out $6$ instructions as follows:

1. The mic holder, Amelia, yells their partner’s name, Bubba. The following illustrates this instruction.
   

2. The mic is passed to the person behind Amelia, Bubba. The following illustrates this instruction.
   

3. The mic is passed to the person behind Bubba, Kiryu.

4. Kiryu yells their partner’s name, Coco.

5. The mic is passed to the person in front of Kiryu, Bubba. The following illustrates this instruction.
   

6. Bubba will yell their partner’s name, Amelia.

Since no one has moved, the line at the end of the $6$ instructions will still be the same.

In the second sample, the line will at first be the same as above. Then, the host calls out $16$ instructions as follows:

1. The mic is passed to the person behind Amelia, Bubba.

2. Bubba passes the mic to Kiryu, then moves to the back of the line. The line formation is now Amelia, Kiryu, Coco, Ollie, Udin, and Bubba. The following illustrates this instruction.
   

3. Kiryu passes the mic to Coco. In the next instruction, Coco yells "Kiryu" into the mic.

4. Coco passes the mic to Ollie, then moves to the back of the line. The line formation is now Amelia, Kiryu, Ollie, Udin, Bubba, and Coco.

5. Ollie passes the mic to Kiryu, who then passes it to Amelia. In the next instruction, Amelia yells "Bubba" into the mic.

6. Amelia passes the mic to Kiryu, then moves to the back of the line. The line formation is now Kiryu, Ollie, Udin, Bubba, Coco, and Amelia.

7. The next $5$ operations moves the mic to the last person in line, Amelia.

8. Amelia passes the mic to Kiryu, then moves to the back of the line. The line formation doesn’t change.

9. Kiryu yells out their partner’s name, Coco.

Thus, at the end, the line will be Kiryu, Ollie, Udin, Bubba, Coco, and Amelia.

Note that the third sample is the second sample will additional instructions appended, as such, we shall continue from the $17$-th operation to the end. In the third sample, the host will call out the last $6$ instructions as follows:

1. Kiryu passes the mic to Ollie, then moves to behind Coco. The line formation is now Ollie, Udin, Bubba, Coco, Kiryu, and Amelia.
   

2. Ollie passes the mic to Udin, who then passes the mic to Bubba.

3. Bubba passes the mic to Coco, then moves to behind Amelia. The line formation is now Ollie, Udin, Coco, Kiryu, Amelia, and Bubba.

4. Coco passes the mic to Udin.

5. Udin yells out their partner’s name, Ollie.

Thus, at the end, the line formation will be Ollie, Udin, Coco, Kiryu, Amelia, and Bubba.

Warning

The I/O files are large. Please use fast I/O methods.

3 6
amelia bubba
kiryu coco
ollie udin
PBBPFP

bubba
coco
amelia

amelia
bubba
kiryu
coco
ollie
udin

3 16
amelia bubba
kiryu coco
ollie udin
BRBPRFFPRBBBBBRP

kiryu
bubba
coco

kiryu
ollie
udin
bubba
coco
amelia

3 22
amelia bubba
kiryu coco
ollie udin
BRBPRFFPRBBBBBRPCBBCFP

kiryu
bubba
coco
ollie

ollie
udin
coco
kiryu
amelia
bubba