Swapping Pieces on a Chessboard Puzzle

In this puzzle, you are given a wooden box with 2N+1 cells arranged in a row. There are N white pieces and N black pieces. Initially, the white pieces occupy the left N cells and the black pieces occupy the right N cells, with the middle cell empty. The initial configuration is therefore:

W...W_B...B

The goal is to exchange the positions of the white and black pieces such that the configuration becomes:

B...B_W...W

There are two types of moves allowed:

• You can move a piece to an adjacent empty cell.
• You can jump a piece over exactly one piece of the opposite color if the landing cell is empty. (That is, if a white piece has a black piece immediately adjacent and the cell just beyond it is empty, then the white piece can jump to that cell; and vice versa for the black piece.)

For example, consider the case when N = 3. The board has 7 cells. The following is one optimal solution (with the minimum number of moves) showing the sequence of board states from the initial to the goal configuration:

WWW_BBB
WW_WBBB
WWBW_BB
WWBWB_B
WWB_BWB
W_BWBWB
_WBWBWB
BW_WBWB
BWBW_WB
BWBWBW_
BWBWB_W
BWB_BWW
B_BWBWW
BB_WBWW
BBBW_WW
BBB_WWW

Your task is to write a program that, given the board size N (1 ≤ N ≤ 12), finds an optimal sequence of moves (i.e. with the fewest moves) that transforms the initial configuration into the target configuration. The program should print each board state on a separate line.

inputFormat

The input consists of a single integer N (1 ≤ N ≤ 12) representing the number of white pieces (and also the number of black pieces).

outputFormat

Output the sequence of board states, one state per line. The first line should be the initial configuration and the last line should be the goal configuration. Each configuration is represented as a string of length 2N+1 using characters 'W' (white), 'B' (black), and '_' (empty).

sample

1

W_B
WB_
_BW
B_W