2006/2007 ACM International Collegiate Programming Contest

University of Ulm Local Contest

# Problem D: Dihedral groups

Source file: dihedral.(c|cc|hs|java|pas)

Input file: dihedral.in

Consider *n* points on a unit circle with numbers
*k = 0, 1, ..., n-1*.
Initially point *k* makes an angle of
*360 · k / n*
degrees to the
x-axis,
measured in counter-clockwise direction.
We are going to perform two different kind of operations on that set
of points:

- rotation by
*360 / n* degrees in clockwise direction
- reflection with respect to the x-axis

The following picture shows an example of these operations:

Given a sequence of operations, we are interested in the shortest
sequence of operations which gives the same result, i.e., the position
of every single point is the same
after performing either of those sequences of operations.

The sequence is given as a string consisting of the characters 'r'
and 'm' which represent clockwise rotation and reflection
respectively ("to the right" and "mirror").
Multiple consecutive occurrences of the same character are collected
into the representation
<character><number>, and for convenience this will also be
done for single occurrences.
So "rrmrrrrrrrrrrrr" will be abbreviated to "r2 m1 r12".
The representations of different operations are always separated by a single space.

#### Input Specification

The input file consists of several test cases.
Each test case starts with a line containing *n* (*3 ≤ n ≤ 10*^{8}), the
number of points.
The second line of each test case consists of an abbreviated
sequence of operations as described above.
All numbers will be positive and less than *10*^{8}.
There will be no empty line in the input file, and no line will contain more than *100000* characters.
The last test case is followed by a line containing 0.

#### Output Specification

For each test case print one line containing the abbreviated
format of the sequence with the minimum number of operations which
results in the same configuration of points as the
input sequence. In case of multiple optimal solutions, print any
solution.

#### Sample Input

4
r2
100
m1 r100 m1
54
r218 m3 r1
0

#### Sample Output

r2
r1 m1

*Note that the second line of the sample output is a blank line*