Princess Celestia and Princess Luna will soon be abdicating the throne to allow for the formal succession of their protégée Princess Twilight Sparkle. In the transition, they have decided to go on vacation, giving Twilight some experience in managing the matters of the castle.
Celestia and Luna have prepared a bucket list of $N$ activities they want to do together. Unfortunately, their likes are wildly different, and so each activity on their list is enjoyed by exactly one of them.
Now, they intend to go through each of the activities in their list in order, but this brings an issue: if they do two activities in a row that only one of them enjoys, then the other one will be quite displeased!
Let’s call a list acceptable if no two consecutive activities on the list are enjoyed by the same princess.
They intend to transform their list into an acceptable one. To make things a little more interesting, they are limited to making the following type of move: choosing some non-empty prefix of their list (possibly the whole list), reversing this prefix, and then shifting it to the end of their list.
They’re already itching to start their sojourn, so they want to have their itinerary fixed as soon as possible. Help them make their list acceptable with the minimum number of moves!
If it is not possible to make their list acceptable, you should also let them know.
The first line of input contains a single integer $N$ ($2 \leq N \leq 300\, 000$), the number of activities on their list.
The second line of input contains a string of $N$ characters. In particular, the $i^\text {th}$ of these characters describes who enjoys the $i^\text {th}$ activity:
a C means this activity is enjoyed by Celestia, and
an L means this activity is enjoyed by Luna.
It is guaranteed that their list is not already acceptable.
If it is not possible to make their list acceptable, output a single line containing the string IMPOSSIBLE.
Otherwise, on the first line, output a single integer $m$, the minimum number of moves necessary to make their list acceptable.
Then, on the second line, output $m$ integers $l_1, l_2, \dots , l_ m$ ($1 \leq l_ i \leq N$), denoting the moves they should perform. In particular, the $i^\text {th}$ move should consist of taking the prefix of length $l_ i$, reversing it, then shifting it to the end.
If there are multiple correct answers, you can output any of them.
The input will be such that if a solution exists, then a solution exists with $m \leq 2\cdot 10^6$.
Sample Input 1 | Sample Output 1 |
---|---|
6 CCLLLC |
3 3 1 4 |
Sample Input 2 | Sample Output 2 |
---|---|
6 CCCCCC |
IMPOSSIBLE |