Alternating Chess Pieces Puzzle

There are 2n chess pieces arranged initially in a row. The first n pieces are white and the last n pieces are black. The board is assumed to be unbounded, so besides these 2n pieces there are many empty cells. In each move you must choose two adjacent pieces (i.e. pieces occupying two consecutive cells) and move them as a block (keeping their order) to a pair of two consecutive empty cells. Moreover, the moved block must jump over at least one piece; that is, the block cannot simply slide into the immediately adjacent empty cells – there must be at least one cell between the original block and its destination.

The goal is to rearrange the pieces so that they become contiguous (i.e., occupy consecutive cells) and the colors alternate (white and black alternate). For example, when n = 5 the final configuration should be something like:

W B W B W B W B W B

Your task is to print the entire moving process. Print the board configuration at the beginning and after every move. In the board configuration, print a character for each cell in the minimal interval covering all pieces. Use 'W' for a white piece, 'B' for a black piece, and '.' for an empty cell.

Note: A move is defined as taking two pieces that are in adjacent cells and shifting them as a unit (without swapping their order) to two consecutive empty cells; the destination cells must be separated from the original position by at least one intervening cell (i.e. the block must jump over at least one piece).

Example (for n = 1):

Input:
1
Output:
WB

inputFormat

The input consists of a single integer n (n ≥ 1), indicating the number of white pieces (and also the number of black pieces).

outputFormat

Print the board configuration after each move (including the initial configuration). In each board configuration, only print the minimal contiguous segment from the smallest occupied cell to the largest occupied cell. In that segment, use 'W' for a white piece, 'B' for a black piece, and '.' for an empty cell. If no moves are needed (i.e. the initial configuration already forms a contiguous alternating sequence), print only the initial configuration.

sample

1

WB