447. Optimal Rest

Time limit per test: 1 second(s)
Memory limit: 262144 kilobytes
input: standard
output: standard

Music Macro Language (MML) is a language for textual representation of musical scores. Although there are various dialects of MML, all of them provide a set of commands to describe scores, such as commands for notes, rests, octaves, volumes, and so forth. In this problem, we focus on rests, i.e. intervals of silence. Each rest command consists of a command specifier '
R
' followed by a duration specifier. Each duration specifier is basically one of the following numbers: '
1
', '
2
', '
4
', '
8
', '
16
', '
32
', and '
64
', where '
1
' denotes a whole (1), '
2
' a half (1/2), '
4
' a quarter (1/4), '
8
' an eighth (1/8), and so on. This number is called the base duration, and optionally followed by one or more dots. The first dot adds the duration by the half of the base duration. For example, '
4.
' denotes the duration of '
4
' (a quarter) plus '
8
' (an eighth, i.e. the half of a quarter), or simply 1.5 times as long as '
4
'. In other words, '
R4.
' is equivalent to '
R4R8
'. In case with two or more dots, each extra dot extends the duration by the half of the previous one. Thus '
4..
' denotes the duration of '
4
' plus '
8
' plus '
16
', '
4...
' denotes the duration of '
4
' plus '
8
' plus '
16
' plus '
32
', and so on. The duration extended by dots cannot be shorter than '
64
'. For exapmle, neither '
64.
' nor '
16...
' will be accepted since both of the last dots indicate the half of '
64
' (i.e. the duration of 1/128). In this problem, you are required to write a program that finds the shortest expressions equivalent to given sequences of rest commands.
Input
The input consists of a line containing a non-empty sequence of valid rest commands. You may assume that the sequence does not contain more than 100000 characters.
Output
Your program should output the shortest expression in one line. If there are multiple expressions of the shortest length, output the lexicographically smallest one.
Example(s)
sample input
sample output
R2R2
R1

sample input
sample output
R1R2R4R8R16R32R64
R1......

sample input
sample output
R1R4R16
R16R1R4


Online Contester Team © 2002 - 2010. All rights reserved.