Пісочний годинник

У цій задачі вам потрібно розв'язати головоломку на плоскій дошці з фішками.

Головоломка "Пісочний годинник" розміру $n$ виглядає так. Дошка розташована на площині і складається з (2 \cdot n + 1) рядків. Рядки горизонтальні і розміщені один під одним. Кожен рядок складається з позицій: середній рядок містить одну позицію, а кожен наступний рядок вище і нижче середнього містить на одну позицію більше, ніж сусідній рядок, ближчий до середини. Позиції сусідніх рядків з'єднані так, що кожна позиція в коротшому рядку має точно два сусіди в більшому рядку. Дошка для n = 2 зображена нижче.

На дошці розміщено кілька фішок. Спочатку кожна позиція у $n$ верхніх рядках містить червону фішку (пісок), а кожна позиція у $n$ нижніх рядках містить синю фішку (повітря). Мета головоломки - поміняти місцями розташування фішок, тобто заповнити верхні $n$ рядків повітрям, а $n$ нижніх рядків піском. Фішки одного кольору вважаються однаковими. У кожній позиції під час будь-якого переміщення може знаходитися не більше однієї фішки. Початковий і фінальний стан для n = 2 представлено нижче. Червоні фішки позначені "X", а сині "O".

Переміщення фігур відбувається згідно з наступними правилами.

• Червоні фішки можуть переміщатися тільки вниз, тоді як сині тільки вгору.

• Під час ходу тільки одна фішка змінює своє положення.

• Якщо для деякої фішки одна з двох сусідніх позицій у дозволеному напрямку (вгору-вліво або вгору-вправо для синіх, вниз-вліво або вниз-вправо для червоних) існує і вільна, то вона може туди переміщуватися.

• Якщо така позиція зайнята фішкою іншого кольору, але наступна позиція в тому ж напрямку (вгору-вліво, вгору-вправо, вниз-вліво, вниз-вправо) існує і вільна, то фішка може перестрибнути і зайняти цю позицію.

• Стрибок допустимий, тільки якщо він здійснюється по прямій, його довжина складає дві позиції і відбувається через фішку іншого кольору. Інші види стрибків (наприклад, прямо вгору або прямо вниз через дві позиції) не допустимі.

Нижче наведено приклад послідовності ходів для розв'язання головоломки при n = 2.

Послідовність ходів записується наступним чином.

• Хід або стрибок вгору-вліво позначається літерою «b».

• Хід або стрибок вгору-вправо позначається літерою «d».

• Хід або стрибок вниз-вліво позначається літерою «p».

• Хід або стрибок вниз-вправо позначається літерою «q».

Інтуїтивне позначення нотації полягає в тому, що хвостик літери показує напрямок переміщення або стрибка.

Виявляється, що наведена нотація забезпечує відновлення всіх проміжних станів головоломки.

За розміром $n$ головоломки виведіть її розв'язання. Не слід мінімізувати або максимізувати кількість ходів.