Andrew the Ant

Andrew the Ant is fascinated by the behavior of his friends. Thousands of them are marching their paths on and on. They can build highly organized ant-hills. Sometimes, however, they act a little bit stupidly.

Recently, Andrew watched his fellow ants marching on top of a long piece of wood. He noticed their behavioral pattern is very simple: Each ant walks slowly forward with a constant speed of $1\, \mathrm{cm}$ per second. Whenever it meets another ant, both of them only touch with their antennae and immediately turn around and walk the opposite direction. If an ant comes to the end of the wood, it falls down and does not affect other ants anymore.

Your task is to simulate the movement of ants. For simplicity, suppose that the ants have zero size (although the picture could suggest something else).

The input consists of several scenarios, at most
$5$. Each scenario starts
with a line containing two integer numbers $L$ and $A$, separated by a space.
$L$ is the length of the
wood in centimetres ($1 \leq L
\leq 99\, 999$), and $A$ is the number of ants at the
beginning of the simulation ($1
\leq A \leq L + 1$). Then there are $A$ lines, each containing a
non-negative integer $X_
i$, one space, and an uppercase letter. The number
($0 \leq X_ i \leq L$)
specifies the position of the $i$-th ant and the letter its initial
direction: either “`L`” for left
(towards zero) or “`R`” for right. No
two ants will start at the same position.

For each scenario, you should print a single line containing
the text “`The last ant will fall down in
$T$ seconds - started at
$P$.`”, where
$T$ is the exact time when
the last ant (or two) reaches the end of the wood, and
$P$ is the position where
that particular ant has originally started in time $0$. If two last ants fall down at the
same time, print “`started at $P$ and $Q$`”, indicating both of their
positions, $P < Q$.

Sample Input 1 | Sample Output 1 |
---|---|

90000 1 0 R 10 1 0 L 14 5 3 L 6 L 13 L 8 R 1 R |
The last ant will fall down in 90000 seconds - started at 0. The last ant will fall down in 0 seconds - started at 0. The last ant will fall down in 13 seconds - started at 6 and 8. |