Dihedral Groups

Consider $n$ points on a unit circle, numbered $k = 0, 1, \ldots, n-1$. Initially point $k$ sits at an angle of $360 \cdot k / n$ degrees from the positive $x$-axis, measured counter-clockwise. Two kinds of operations may be applied to the whole set of points:

• $r$ — a rotation by $360 / n$ degrees in the clockwise direction ("to the right").
• $m$ — a reflection across the $x$-axis ("mirror").

Given a sequence of such operations, we want the shortest sequence of operations that produces exactly the same final configuration, i.e. every single point ends in the same position after either sequence.

A sequence is written as a string over the characters r and m. Consecutive equal characters are grouped into the form <character><count>, and this is done even for a single occurrence. For example, rrmrrrrrrrrrrrr is abbreviated as r2 m1 r12. Different groups are always separated by a single space.

The input consists of several test cases. Each test case begins with a line holding $n$ ($3 \le n \le 10^8$), the number of points. The next line holds an abbreviated sequence of operations as described above. Every count is a positive integer smaller than $10^8$. No line is empty and no line exceeds $100000$ characters. The last test case is followed by a line containing a single $0$, which must not be processed.

For each test case, print on its own line the abbreviated form of a shortest sequence that reaches the same final configuration as the input sequence. If that shortest sequence is empty (the input has no net effect), print an empty line.

When several shortest sequences exist, print the canonical one, chosen by applying these rules in order:

1. use the fewest reflection operations m;
2. if a tie remains, make the sequence start with a rotation r.

These rules single out exactly one sequence for every input.