Time Limit: 1000 ms
Memory Limit: 65535 ms
Consider n points on a unit circle with numbers k = 0, 1, ..., n-1. Initially point k makes an angle of 360 · k / n degrees to the x-axis, measured in counter-clockwise direction. We are going to perform two different kind of operations on that set of points:
The following picture shows an example of these operations:
Given a sequence of operations, we are interested in the shortest sequence of operations which gives the same result, i.e., the position of every single point is the same after performing either of those sequences of operations.
The sequence is given as a string consisting of the characters 'r' and 'm' which represent clockwise rotation and reflection respectively ("to the right" and "mirror"). Multiple consecutive occurrences of the same character are collected into the representation <character><number>, and for convenience this will also be done for single occurrences. So "rrmrrrrrrrrrrrr" will be abbreviated to "r2 m1 r12". The representations of different operations are always separated by a single space.