二面体群

题目描述

考虑在一个单位圆周上的 $n$ 个点,$n$ 个点的标号为 $K=0,1,\ldots,n-1$。初始的时候 $K$ 相对于 X 轴的角度为 $\dfrac{360 \times k}{n}$ 度,这里的角度是相对于 X 轴的逆时针角度。我们将在这组点上运行 2 种不同类型的操作: 1. 顺时针旋转 $\dfrac{360}{n}$度 2. 相对于 X 轴的映射 对于给定的操作序列,如果结果相同,我们只对最短的操作序列感兴趣。结果相同是指对于不同的操作序列,最后的操作结果中每一个单一点的位置都是一样的。 操作序列以字符串的形式给出,该字符串中只含有字母 `r` 和 `m`。`r` 代表顺时针旋转,`m` 代表单独映射(到右边并且对称)。字符串中如果有多个字母连续出现要简写成 `<字母><数字>` 的形式,为了方便起见,字母如果单独出现也写成这种形式。如 `rrmrrrrrrrrrrrr` 可以写成 `r2 m1 r12`,每个操作序列一行。

输入输出格式

输入格式


输入共两行。 第一行一个数 $N$,表示圆周上点的个数。 第二行为按上面的方式缩写的操作序列,所有的数字都是正整数,并且小于$10^8$ 。在输入文件中没有空行,并且每一行的字符个数都小于 $10^5$。

输出格式


输出最短操作序列。若无需操作则什么都不输出。

输入输出样例

输入样例 #1

54
r218 m3 r1

输出样例 #1

r1 m1

说明

$100\%$ 的数据满足 $3 \leq N \leq 10^8$。