Смужка#3845

Смужка

0,5 секунди

256 мегабайтів

Дуже легка

Нехай $k$ — деяке додатне ціле число. Маємо паперову смужку з $n = 2^{k}$ n = 2^k клітинками. Клітинки пронумеровані зліва направо числами від $1$ до $n$ . Ось як виглядає смужка спочатку (це вид збоку, а не зверху!) для $k = 3$ k = 3, відповідно для $n = 8$ n = 8:

1 2 3 4 5 6 7 8

Смужку можна згортати наступним чином: вона фіксується посередині, одна частина залишається нерухомою, тоді як інша загортається наверх або вниз. Спочатку права половина загортається наверх. Потім ліва половина загортається вниз, і нарешті, ліва половина йде наверх. Ось як виглядає смужка після кожної дії:

Як бачимо, числа на смужці зверху вниз розташовані в такому порядку: 7, 2, 3, 6, 5, 4, 1, 8.

Це те, що нам потрібно знайти. $k$ у цьому завданні фіксоване і дорівнює $21$ . Отже, у нас є смужка з $2^{21}$ 2^{21} клітинками; ця смужка згинається $21$ раз, відповідно до послідовності інструкцій згортання: LU (згинаємо ліву половину вгору), LD (згинаємо ліву половину вниз), RU (згинаємо праву половину вгору) або RD (згинаємо праву половину вниз). Нам потрібно визначити порядок чисел на складеній смужці. Точніше, нам потрібно знати $1024$ числа — вони повинні з'явитися на виході.

Вхідні дані

Містить інструкції згортання і складається з $21$ рядка — кожен рядок містить два символи: LU, LD, RU або RD. $m$ -й рядок містить опис $m$ -го ( $1 \leq m \leq 21$ 1 \leq m \leq 21) згину.

Вихідні дані

Вихід складається рівно з $1024$ рядків. $m$ -й рядок ( $1 \leq m \leq 1024$ 1 \leq m \leq 1024) містить $m$ -те число зверху.

Приклади

Зразки даних занадто великі, щоб показати на папері, але якщо $k = 3$ k = 3 і вам потрібно вивести перші $5$ чисел, вихід виглядає наступним чином:

Приклад 1