A10014 | Walking!

There is a sand trail in front of Alice's home.

In daytime, people walk over it and leave a footprint on the trail for their every single step. Alice cannot distinguish the order of the footprints, but she can tell whether each footprint is made by left foot or right foot. Also she's certain that all people are walking by alternating left foot and right foot.

For example, suppose that one person walked through the trail and left some footprints. The footprints are RRLRL in order along the trail ('R' means right foot and 'L' means left foot). You might think the outcome of the footprints is strange. But in fact, some steps are resulting from walking backwards!

There are some possible order of steps that produce these footprints such as $1→3→2→5→4$ or $2→3→4→5→1$ (we suppose that the distance between two consecutive steps can be arbitrarily long). The number of backward steps from above two examples are $2$ and $1$ separately.

Alice is interested in these footprints. Whenever there is a person walking trough the trail, she takes a picture of all these footprints along the trail and erase all of them so that next person will leave a new set of footprints. We know that people walk by alternating right foot and left foot, but we don't know if the first step is made by left foot or right foot.

Alice wants to know the minimum possible number of backward steps made by a person. But it's a little hard. Please help Alice to calculate it. You also need to construct one possible history of these footprints.

Only one line containing the string $S$ ( $1<=|S|<=100000$ ) containing all footprints in order along the trail from entrance to exit.

It is guaranteed that there is at least one possible footprint history.

You should output $2$ lines.

The first line should contain a number denoting the minimum number of backward steps.

The second line should contain a permutation of integers from 1 to $|S|$ . This permutation should denote the order of footprints that may possible be used by person walked there.

If there are several possible answers, you may output any of them.