영어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)
시간 제한 1초 · 메모리 제한 512 MB
Problem
There are 2n boxes in a line. Two adjacent boxes are empty, and all other boxes have a letter "A" or "B". Both letters appear in exactly n-1 boxes.
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 ≤ 1000.
If there are no solutions, print only "-1".
Constraints
- 1 ≤ n ≤ 100
예제
예제 1
3 AB..BA
2 ABBA.. A..ABB
예제 2
3 ABAB..
-1