Пісочний годинник
У цій задачі вам потрібно розв'язати головоломку на плоскій дошці з фішками.
Головоломка "Пісочний годинник" розміру 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» і не містити жодних інших символів, навіть пробілів. Якщо існує декілька розв'язань, виведіть будь-яке.