Description

Given a chain of N (1 ≤ N ≤ 10⁶) balls colored either red (‘R’), green (‘G’) or blue (‘B’) and numbered sequentially 1 through N from left to right, a game proceeds as follows:

1. Pick the leftmost segment containing the largest number of consecutive balls of the same color.
2. If the segment contains only one ball, the game ends; otherwise dislodge it from the chain. If the remaining balls are broken into two chains, join them maintaining their order.
3. Report the color and numbers of the removed balls.
4. Go back to step 1 if any balls remain.

Write a program to simulate the process of a game.

Input

The input contains only a string of ‘R’s, ‘G’s and ‘B’s representing the balls in the chain from left to right.

Output

For each segment dislodged, output whatever is reported following the sample output’s example.

GRRBBBRRGB

B 4 5 6
R 2 3 7 8
G 1 9

Source

POJ Founder Monthly Contest – 2007.12.30, frkstyc