balls

balls

Let's take the following game:
Initially, the player has available a row of black and red balls, lined up in random order in the top part of the screen. A mobile firing device is placed in the lower part of the screen. The device launches balls (black and red) which are inserted into the initial row, the succession of balls being known. Supposing that, at one time, the row of balls is made up of n balls, a ball launched by the firing device can be inserted into the row between ball 1 and ball 2, between ball 2 and ball 3,…, or between ball n-1 and ball n, as can be observed in the image below.

Fig. 1

If the row contains a single ball, inserting a ball can be done to its right.
If after an insertion there are at least three consecutive balls of the same color in the row, these will disappear, and this rule will apply to the remaining balls.
For the configuration in Fig. 1, a ball insertion possibility is:
Step 1. Insert the first ball (red) between ball 3 and ball 4:

Fig. 2

Step 2. Insert the second ball (red) to the right of the only remaining ball:
Step 3. Insert the third ball (black ) between ball 1 and ball 2:

Fig. 3

Task

Write a program that determines the minimum number of balls that must be launched so that the initial row of balls become empty or, if this is not possible, determine all the minimum length rows of balls that can be obtained by launching all available balls in the launching device.

Input Data

File balls.in contains on line one a row of characters describing the initial row of balls, character b representing a black colored ball and character r representing a red colored ball. Line two contains a row of characters describing the succession in which the balls are launched from the firing device, character b representing a black colored ball and character r representing a red colored ball.

Output Data

File balls.out will contain on line one the minimum number of balls that have to be launched to transform the initial row into an empty row, if this is possible. Otherwise, the output file will contain all the ball rows of minimum length that can be obtained by launching all the available balls from the launching device, one row per line, in lexicographical order.

Constraints

The sum of the number of balls from the initial row and the number of balls from the launching device is a positive integer between 2 and 13.

Examples

balls.in	balls.out	Explanations	balls.in	balls.out	Explanations
rbbrrb rrb	rbr rrb	The first solution is obtained as per the explanations in the task. The second solution is obtained as follows: -we insert the first ball between bal 1 and ball 2 => rrbbrrb -we insert the second ball between ball 1 and ball 2 =>rrrbbrrb => bbrrb -we insert the third ball between ball 1 and ball 2=>bbbrrb => rrb	rrbrr bbrb	2	If we insert the first two balls, consecutively, between ball 2 and ball 3 we obtain the following successive configurations: rrbbrr => rrbbbrr => empty row

Time limit: 1 second/test
Total available memory: 70 MB, of which 6 MB for the stack.

prof. Alin Burta
"B.P. Haşdeu" Buzău National High School
Contact: allbu2003@yahoo.com