P2250 Dihedral Group

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.

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 the shortest operation sequence. If no operation is needed, output nothing.

$100\%$ of the testdata satisfies $3 \leq N \leq 10^8$. Translated by ChatGPT 5