- Time limit: 1.00 s
- Memory limit: 512 MB
Your task is to move the letters so that all letters "A" appear before any letter "B". On each turn you can choose any two adjacent boxes that have a letter and move the letters to the two adjacent empty boxes, preserving their order.
It can be proven that either there is a solution that consists of at most $10n$ turns or there are no solutions.
Input
The first line has an integer $n$: there are $2n$ boxes.
The second line has a string of $2n$ characters which describes the starting position. Each character is "A", "B" or "." (empty box).
Output
First print an integer $k$: the number of turns. After this, print $k$ lines that describe the moves. You can print any solution, as long as $k \le 1000$.
If there are no solutions, print only "-1".
Constraints
- $1 \le n \le 100$
Input:
3
AB..BA
Output:
2
ABBA..
A..ABB
Example 2
Input:
3
ABAB..
Output:
-1