二面体群

题目描述

考虑在一个单位圆周上的 n个点，n个点的标号为K=0，1，……n-1。初始的时候K相对于X轴的角度为：360 * k / n 度，这里的角度是相对于X轴的逆时针角度。我们将在这组点上运行2 种不同类型的操作：

1.顺时针旋转360/n度

2.相对于X轴的映射

对于给定的操作序列，如果结果相同，我们只对最短的操作序列感兴趣。结果相同是指对于不同的操作序列，最后的操作结果中每一个单一点的位置都是一样的。

操作序列以字符串的形式给出，该字符串中只含有字母“r”和“m”。 “r”代表顺时针旋转，“m”代表单独映射（到右边并且对称）。字符串中如果有多个字母连续出现要简写成<字母><数字>的形式，为了方便起见，字母如果单独出现也写成这种形式。如"rrmrrrrrrrrrrrr"可以写成"r2 m1 r12"，每个操作序列一行。

输入输出格式

输入共两行。

第一行共一个数N，表示圆周上点的个数。

第二行为按上面的方式缩写的操作序列，所有的数字都是正整数，并且小于108 。在输入文件中没有空行，并且每一行的字符个数都小于100000。

输出共一行。

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

输入输出样例

54
r218 m3 r1

r1 m1

说明

[数据范围]

100%的数据，3 <= N <= 108