Problem A
Number Line Artwork

Illustration of final state in sample 1

Otto the octopus loves to make number line artworks. Whenever Otto makes an artwork, he first places each of his $n$ arms on the integers $0,1,\dots n-1$ along the number line. Then he makes a mark with each of his arms; the marks can be in different colors depending on Otto’s mood. To finish the artwork, Otto then does $m$ actions, each of which is one of the following:

• moving an arm leftwards to the next mark, or

• moving an arm rightwards to the next mark, or

• making a new mark.

When Otto makes a new mark, he always makes the mark exactly halfway between two existing marks. More specifically, if Otto uses his $i$th arm to make a new mark, the new mark will be in the space immidiately to the left of the mark that the $i$th arm was previously resting with. After constructing the new mark, the $i$th arm will rest with the mark it just made. Otto will never make a new mark with an arm resting on a non-positive number.

Given the colors of the first $n$ marks and the list of actions, what will be the order of the colors in the final artwork?

Input

The first line contains two integers, $n$ the number of arms, and $m$ the number of actions. On the second line, there are $n$ space-separated strings indicating the colors of the initial marks, starting with the color of the mark at 0.

Thereafter follows $m$ lines, one for each action. Each such line contains an integer $i$ (the number of the arm preforming the action) and a string $w$ (indicating which action to be preformed). If the string $w$ is exactly “L” or “R”, that indicates that the arm is moving one mark to the left or to the right, respectively. Otherwise, the string $w$ indicates the color of the created mark.

You may assume colors are always written in lowercase, and that there never will be a sequence of moves such that an arm moves “out of range” of the marks. You may also assume that the following constraints are met:

• $1\le n,m\le 100000$

• For each action, $0\le i<n$ and $|w|\le 10$

Output

Output a single line with the colors of the final artwork in order from left to right. Each color should be separated with a single space.

3 5
red blue green
0 R
0 R
0 gold
1 black
2 purple

red black blue gold purple green

2 6
a b
0 R
0 b
1 L
1 a
0 R
0 c

a a b c b