Minimal Operation Sequence on a Unit Circle

Consider (n) points on the circumference of a unit circle, numbered (0,1,\ldots,n-1). Initially, the point with label (k) is positioned at an angle of (\frac{360\times k}{n}) degrees measured counterclockwise from the positive x-axis. Two types of operations can be performed on these points:

1. A clockwise rotation by (\frac{360}{n}) degrees, denoted by (r).
2. A reflection about the x-axis, denoted by (m).

The operations are given as a compressed sequence where consecutive occurrences of the same letter are written in the format <letter><number>. For example, the sequence rrmrrrrrrrrrrrr is written as r2 m1 r12 (even a single occurrence is expressed in this form).

Different operation sequences may yield the same final configuration (i.e. each point ends up in the same position). In that case, only the shortest sequence (in terms of the total number of operations) equivalent to the given sequence is of interest. The output must also follow the compressed format.

Transformation Group Insight: The operations (r) and (m) generate the dihedral group (D_n) with the relations: [ r^n = e, \quad m^2 = e, \quad m,r = r^{-1},m. ] Thus any sequence is equivalent to either a pure rotation (r^a) or a reflection (r^a m) for some (a) (with operations taken modulo (n)).

Minimal Sequence Rules:

• If the resulting transformation is a pure rotation (r^a) with (a \neq 0), output it as r<a>.
• If it is the identity (i.e. (r^0)), output r0.
• If it is a reflection with no additional rotation (i.e. (r^0 m)), output m1.
• Otherwise, for a reflection with a rotation part (i.e. (r^a m) with (a \neq 0)), output r<a> m1.

The input format and expected output are detailed below.

inputFormat

The input consists of two parts:

1. A line containing an integer (n) (the number of points on the unit circle).
2. A line containing the compressed operation sequence. Each operation is in the format <letter><number>, where the letter is either r (for a clockwise rotation by (360/n) degrees) or m (for a reflection about the x-axis).

For example:

4 r1 m1 r1

outputFormat

Output a single line containing the minimal equivalent operation sequence in the compressed format as described. For instance, based on the rules:

• If the overall transformation is a rotation (r^a) (with (a \neq 0)), output: r<a>.
• If it is the identity transformation, output: r0.
• If the transformation is a reflection with no rotation, output: m1.
• Otherwise, for a reflection with rotation part, output: r<a> m1.

sample

4
r1 m1 r1

m1