Песочные часы
В этой задаче Вам необходимо решить головоломку на плоской доске с фишками.
Головоломка "Песочные часы" размера n выглядит следующим образом. Доска расположена на плоскости и состоит из (2 ∙ n + 1) строк. Строки горизонтальны и лежат одна под другой. Каждая строка состоит из позиций: средняя строка содержит одну позицию, а каждая следующая строка выше и ниже средней содержит на одну позицию больше соседней строки, которая ближе к середине. Позиции соседних строк соединены таким образом, что каждая позиция в коротком ряду имеет в точности два соседа в большем ряду. Доска для n = 2 приведена ниже.
На доске находится несколько фишек. Изначально каждая позиция n верхних строк содержит красную фишку (песок), а каждая позиция n нижних строк содержит синюю фишку (воздух). Цель головоломки - поменять местами расположение фишек, то есть заполнить верхние n рядов воздухом, а n нижних рядов песком. Фишки одного цвета считаются одинаковыми. В каждой позиции во время любого перемещения может находиться не более одной фишки. Начальное и финальное состояние для n = 2 представлено ниже. Красные фишки обозначены “X”, а синие “O”.
Передвижение фигур происходит согласно следующих правил.
Красные фишки могут передвигаться только вниз, в то время как синие только вверх.
Во время хода только одна фишка меняет свое положение.
Если для некоторой фишки одна из двух соседних позиций в разрешенном направлении (вверх-влево или вверх-вправо для синих, вниз-влево или вниз-вправо для красных) существует и свободна, то она может туда передвигаться.
Если такая позиция занята фишкой другого цвета, но следующая позиция в том же направлении (вверх-влево, вверх-вправо, вниз-влево, вниз-вправо) существует и свободна, то фишка может перепрыгнуть и занять эту позицию.
Прыжок допустим, только если он совершается по прямой, его длина составляет две позиции и происходит через фишку другого цвета. Другие виды прыжков (например, прямо вверх или прямо вниз через две позиции) не допустимы.
Ниже приведен пример последовательности ходов для решения головоломки при n = 2.
Последовательность ходов записывается следующим образом.
Ход или прыжок вверх-влево обозначается буквой «b».
Ход или прыжок вверх-вправо обозначается буквой «d».
Ход или прыжок вниз-влево обозначается буквой «p».
Ход или прыжок вниз-вправо обозначается буквой «q».
Интуитивное обозначение нотации состоит в том что хвостик буквы показывает направление передвижения или прыжка.
Оказывается, что приведенная нотация обеспечивает восстановление всех промежуточных состояний головоломки.
По размеру n головоломки выведите ее решение. Не следует минимизировать или максимизировать количество ходов.
Входные данные
Размер головоломки n (1 ≤ n ≤ 10).
Выходные данные
В одной строке вывести решение головоломки заданного размера. Строка должна содержать только буквы «b», «d», «p» и «q» и не содержать никаких других символов, даже пробелов. Если существует несколько решений, выведите любое.