Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official.
×

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

E. Walking!

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard outputThere 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.

Input

Only one line containing the string *S* (1 ≤ |*S*| ≤ 100 000) containing all footprints in order along the trail from entrance to exit.

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

Output

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.

Examples

Input

RRLRL

Output

1

2 5 1 3 4

Input

RLRLRLRLR

Output

0

1 2 3 4 5 6 7 8 9

Input

RRRRRLLLL

Output

4

4 9 3 8 2 7 1 6 5

Note

For the first sample, one possible order is 2 → 5 → 1 → 3 → 4, among them only the step 5 → 1 is backward step so the answer is 1.

For the second example one possible order is just to follow the order of input, thus there are no backward steps.

For the third sample, there will be 4 backward steps because every step from L to R will be a backward step.

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/12/2018 00:31:50 (f2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|