Stripe
Пусть k - некоторое положительное целое число. Имеется бумажная полоса с n = 2^k ячейками. Ячейки пронумерованы слева направо числами от 1 до n. Вот как полоса выглядит изначально (это вид сбоку, а не сверху!) для k = 3, и соответственно для n = 8:
1 2 3 4 5 6 7 8
Заворачивать полосу можно следующим образом: она фиксируется в середине, одна часть остается не тронутой, в то время как вторая заворачивается наверх или вниз. Сначала правая половина заворачивается наверх. Затем левая половина заворачивается вниз, и наконец, левая половина идет вверх. Вот как выглядит полоса после каждого действия:
Как видим, числа на полосе сверху вниз расположены в следующем порядке: 7, 2, 3, 6, 5, 4, 1, 8.
This is what we need to find. k in this task is fixed and equals 21. So we have a stripe with 2^21 cells; this stripe is folded 21 times, according to a sequence of folding instructions: LU (we bind left half up), LD (we bind left half down), RU (we bind right half up) or RD (we bind right half down). We need to determine the order of the numbers on the folded stripe. More exactly, we need to know 1024 numbers – they should appear on output.
Входные данные
Contains the folding instructions and consists of 21 lines – each line contains two symbols: LU, LD, RU or RD. The m-th line contains the description of the m-th (1 ≤ m ≤ 21) fold.
Выходные данные
Output consists of exactly 1024 lines. The m-th line (1 ≤ m ≤ 1024) contains the m-th number from top.
Sample data are too big to show on paper, but if k = 3 and you have to output the first 5 numbers, the output is the following: