#P2250. 二面体群

二面体群

题目描述

考虑在一个单位圆周上的 nn 个点,nn 个点的标号为 K=0,1,,n1K=0,1,\ldots,n-1。初始的时候 KK 相对于 X 轴的角度为 360×kn\dfrac{360 \times k}{n} 度,这里的角度是相对于 X 轴的逆时针角度。我们将在这组点上运行 2 种不同类型的操作:

  1. 顺时针旋转 360n\dfrac{360}{n}
  2. 相对于 X 轴的映射

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

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

输入格式

输入共两行。

第一行一个数 NN,表示圆周上点的个数。

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

输出格式

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

54
r218 m3 r1
r1 m1

提示

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