Description

Consider $n$ points on a unit circle, labeled $K=0,1,\ldots,n-1$. Initially, the angle of $K$ relative to the X-axis is $\dfrac{360 \times k}{n}$ degrees, measured counterclockwise from the X-axis. We will perform two types of operations on this set of points:

1. Rotate clockwise by $\dfrac{360}{n}$ degrees.
2. Reflect with respect to the X-axis.

For a given operation sequence, if the results are the same, we are only interested in the shortest operation sequence. “Results are the same” means that, for different operation sequences, the final position of each individual point is identical.

Operation sequences are given as strings consisting only of the letters r and m. r denotes a clockwise rotation, and m denotes a reflection about the X-axis. If a letter appears consecutively, it must be abbreviated as . For convenience, a single letter is also written in this form. For example, rrmrrrrrrrrrrrr can be written as r2 m1 r12, one operation sequence per line.

Input Format

The input consists of two lines.

The first line contains an integer $N$, the number of points on the circle.

The second line contains the operation sequence abbreviated as described above. All numbers are positive integers and less than $10^8$. There are no blank lines in the input file, and the number of characters on each line is less than $10^5$.

Output Format

Output the shortest operation sequence. If no operation is needed, output nothing.

54
r218 m3 r1

r1 m1

Hint

$100\%$ of the testdata satisfies $3 \leq N \leq 10^8$.

Translated by ChatGPT 5