이면군(dihedral group)

단위원 위에 $n$개의 점이 있고, 각 점에는 $k = 0, 1, \ldots, n-1$의 번호가 매겨져 있다. 처음에 점 $k$는 양의 $x$축에서 반시계 방향으로 잰 $360 \cdot k / n$도 위치에 놓여 있다. 이 점들의 집합 전체에 다음 두 가지 연산을 적용할 수 있다.

• $r$ — 시계 방향으로 $360 / n$도 회전(오른쪽으로, "to the right").
• $m$ — $x$축에 대한 대칭(거울처럼, "mirror").

연산들의 수열이 주어졌을 때, 같은 최종 배치를 만드는 가장 짧은 연산 수열을 구하려고 한다. 즉, 두 수열을 각각 수행한 뒤 모든 점의 위치가 서로 같아야 한다.

수열은 문자 r와 m으로 이루어진 문자열로 표기한다. 같은 문자가 연속으로 나오면 <문자><개수> 형태로 묶으며, 한 번만 나오더라도 같은 방식으로 표기한다. 예를 들어 rrmrrrrrrrrrrrr는 r2 m1 r12로 축약된다. 서로 다른 묶음은 항상 하나의 공백으로 구분한다.

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스의 첫 줄에는 점의 개수 $n$ ($3 \le n \le 10^8$)이 주어진다. 다음 줄에는 위에서 설명한 축약된 연산 수열이 주어진다. 모든 개수는 $10^8$보다 작은 양의 정수이다. 빈 줄은 없으며, 어떤 줄도 $100000$자를 넘지 않는다. 마지막 테스트 케이스 다음 줄에는 $0$ 하나가 주어지며, 이 줄은 처리하지 않는다.

각 테스트 케이스마다, 입력 수열과 같은 최종 배치를 만드는 가장 짧은 연산 수열을 축약된 형태로 한 줄에 출력한다. 가장 짧은 수열이 비어 있다면(입력이 아무런 변화도 일으키지 않는 경우) 빈 줄을 출력한다.

가장 짧은 수열이 여러 개일 때에는 다음 규칙을 순서대로 적용해 얻는 표준(canonical) 수열을 출력한다.

1. 대칭 연산 m의 개수가 가장 적은 것을 고른다.
2. 그래도 여러 개가 남으면, 회전 r로 시작하는 것을 고른다.

이 규칙은 모든 입력에 대해 정확히 하나의 수열을 결정한다.