Задачи
Песочные часы
Песочные часы
В этой задаче Вам необходимо решить головоломку на плоской доске с фишками.
Головоломка "\textit{Песочные часы}" размера \textbf{n} выглядит следующим образом. Доска расположена на плоскости и состоит из (\textbf{2} ∙ \textbf{n} + \textbf{1}) строк. Строки горизонтальны и лежат одна под другой. Каждая строка состоит из позиций: средняя строка содержит одну позицию, а каждая следующая строка выше и ниже средней содержит на одну позицию больше соседней строки, которая ближе к середине. Позиции соседних строк соединены таким образом, что каждая позиция в коротком ряду имеет в точности два соседа в большем ряду. Доска для \textbf{n} = \textbf{2} приведена ниже.
\includegraphics{https://static.e-olymp.com/content/de/deaf15d6e76084479a5c77b7c6e7942184070b2a.jpg}
На доске находится несколько фишек. Изначально каждая позиция \textbf{n} верхних строк содержит красную фишку (песок), а каждая позиция \textbf{n} нижних строк содержит синюю фишку (воздух). Цель головоломки - поменять местами расположение фишек, то есть заполнить верхние \textbf{n} рядов воздухом, а \textbf{n }нижних рядов песком. Фишки одного цвета считаются одинаковыми. В каждой позиции во время любого перемещения может находиться не более одной фишки. Начальное и финальное состояние для \textbf{n} = \textbf{2} представлено ниже. Красные фишки обозначены “\textbf{X}”, а синие “\textbf{O}”.
\includegraphics{https://static.e-olymp.com/content/ac/ac3fa91be4e1c4615882db7e84df53b00cebb1b5.jpg}
Передвижение фигур происходит согласно следующих правил.
\begin{itemize}
\item Красные фишки могут передвигаться только вниз, в то время как синие только вверх.
\item Во время хода только одна фишка меняет свое положение.
\item Если для некоторой фишки одна из двух соседних позиций в разрешенном направлении (вверх-влево или вверх-вправо для синих, вниз-влево или вниз-вправо для красных) существует и свободна, то она может туда передвигаться.
\item Если такая позиция занята фишкой другого цвета, но следующая позиция в том же направлении (вверх-влево, вверх-вправо, вниз-влево, вниз-вправо) существует и свободна, то фишка может перепрыгнуть и занять эту позицию.
\item Прыжок допустим, только если он совершается по прямой, его длина составляет две позиции и происходит через фишку другого цвета. Другие виды прыжков (например, прямо вверх или прямо вниз через две позиции) не допустимы.
\end{itemize}
Ниже приведен пример последовательности ходов для решения головоломки при \textbf{n} = \textbf{2}.
\includegraphics{https://static.e-olymp.com/content/29/293f2b753481e51c001efc99ca8fa3ea83fe1a88.jpg}
Последовательность ходов записывается следующим образом.
\begin{itemize}
\item Ход или прыжок вверх-влево обозначается буквой <<\textbf{b}>>.
\item Ход или прыжок вверх-вправо обозначается буквой <<\textbf{d}>>.
\item Ход или прыжок вниз-влево обозначается буквой <<\textbf{p}>>.
\item Ход или прыжок вниз-вправо обозначается буквой <<\textbf{q}>>.
\end{itemize}
Интуитивное обозначение нотации состоит в том что хвостик буквы показывает направление передвижения или прыжка.
Оказывается, что приведенная нотация обеспечивает восстановление всех промежуточных состояний головоломки.
По размеру \textbf{n} головоломки выведите ее решение. Не следует минимизировать или максимизировать количество ходов.
\InputFile
Размер головоломки \textbf{n} (\textbf{1} ≤ \textbf{n} ≤ \textbf{10}).
\OutputFile
В одной строке вывести решение головоломки заданного размера. Строка должна содержать только буквы <<\textbf{b}>>, <<\textbf{d}>>, <<\textbf{p}>> и <<\textbf{q}>> и не содержать никаких других символов, даже пробелов. Если существует несколько решений, выведите любое.
Входные данные #1
2
Выходные данные #1
dppdbqbdppqdqbbqdqpdbqb