Number Line Artwork
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, \ldots n1$ 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 nonpositive 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$ spaceseparated 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 \leq n, m \leq 100\, 000$

For each action, $0\leq i < n$ and $w \leq 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.
Sample Input 1  Sample Output 1 

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

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