Description

The signature of a permutation is a string that is computed as follows: for each pair of consecutive elements of the permutation, write down the letter 'I' (increasing) if the second element is greater than the first one, otherwise write down the letter 'D' (decreasing).

For example, the signature of the permutation {3,1,2,7,4,6,5} is "DIIDID". Your task is to reverse this computation: You are given a string signature containing the signature of a permutation. Find and return the lexicographically smallest permutation with the given signature.

Input

multi test case. For each case, one string which contains only 'I' and 'D' represent the signature of the result permutation. I confirm the length of the string is less than 1000.

Output

the permutation of length signature.length()+1

Sample

Input

I
DD
DIDII

Output

1 2
3 2 1
2 1 4 3 5 6