Problem A
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 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 \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 |