Hourglass#7319
In this problem, you have to solve a puzzle involving a planar board and pieces.
The Hourglass Puzzle of size looks as follows. The board is drawn on a plane which consists of (2 \cdot n + 1) rows. The rows are horizontal and lie one under the other. Each row consists of positions: the middle row contains one position, and each other row below or above the middle contains one more position than its neighbor towards the middle. The positions in neighboring rows are connected so that each position of the shorter row has exactly two neighboring positions in the longer one. The board for n = 2 is illustrated below.
There are some pieces on the board. Initially, each position of the top rows contains a red piece (sand), and each position of the bottom rows contains a blue piece (air). The goal of the puzzle is to swap the pieces, that is, to fill top rows by air and bottom rows by sand. Pieces of the same color are considered the same. There can be at most one piece in each position at any given moment. The initial and final positions for n = 2 are illustrated below. Red pieces are denoted by "X" while blue pieces are denoted by "O".
Moving the pieces complies with the following rules.
Red pieces can only move down, while blue pieces can only move up.
On each move, exactly one piece changes its position.
If for some piece, one of the two neighboring positions in the permitted direction (up-left or up-right for blue pieces, down-left or down-right for red ones) exists and is free, that piece can just move there.
If that position is occupied by a piece of the other color, but the next position in the same direction (up-left, up-right, down-left or down-right) exists and is free, the piece can jump into that free position.
Note that jumps are allowed only if they follow a straight line, have a length of two positions and go over a piece of the other color. Other kinds of jumps (for example, straight up or straight down by two rows) are not permitted.
The pictures below illustrate the sequence of moves allowing to solve the puzzle for n = 2.
The sequence of moves can be written down in the following way.
Moving or jumping up-left is denoted by lowercase English letter «b».
Moving or jumping up-right is denoted by lowercase English letter «d».
Moving or jumping down-left is denoted by lowercase English letter «p».
Moving or jumping down-right is denoted by lowercase English letter «q».
The intuitive meaning of this notation is that the tail of each letter shows the direction of a movement or jump.
It turns out that the information provided by such notation is enough to restore all intermediate states of the puzzle.
Given , the size of the puzzle, print out its solution. Note that you don't have to minimize or maximize the number of moves.
The size (1 \le n \le 10) of the puzzle.
Print one line containing a solution to the puzzle of the given size. This line must contain only lowercase English letters «b», «d», «p» and «q» and no other characters, in particular, no spaces. If there are several possible solutions, print any one of them.
Example 1