Задачи
Stripe
Stripe
Пусть \textbf{k }- некоторое положительное целое число. Имеется бумажная полоса с \textbf{n} = \textbf{2^k} ячейками. Ячейки пронумерованы слева направо числами от \textbf{1 }до \textbf{n}. Вот как полоса выглядит изначально (это вид сбоку, а не сверху!) для \textbf{k} = \textbf{3}, и соответственно для \textbf{n} = \textbf{8}:
\textbf{1 2 3 4 5 6 7 8}
Заворачивать полосу можно следующим образом: она фиксируется в середине, одна часть остается не тронутой, в то время как вторая заворачивается наверх или вниз. Сначала правая половина заворачивается наверх. Затем левая половина заворачивается вниз, и наконец, левая половина идет вверх. Вот как выглядит полоса после каждого действия:
\includegraphics{https://static.e-olymp.com/content/a3/a306ae0f698b6e5c79b52a4c07c5105f6d0b93ae.jpg}
Как видим, числа на полосе сверху вниз расположены в следующем порядке: \textbf{7}, \textbf{2}, \textbf{3}, \textbf{6}, \textbf{5}, \textbf{4}, \textbf{1}, \textbf{8}.
This is what we need to find. \textbf{k} in this task is fixed and equals \textbf{21}. So we have a stripe with \textbf{2^21} cells; this stripe is folded \textbf{21 }times, according to a sequence of folding instructions: \textbf{LU} (we bind left half up), \textbf{LD} (we bind left half down), \textbf{RU} (we bind right half up) or \textbf{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 \textbf{1024} numbers -- they should appear on output.
\InputFile
Contains the folding instructions and consists of \textbf{21 }lines -- each line contains two symbols: \textbf{LU}, \textbf{LD}, \textbf{RU} or \textbf{RD}. The \textbf{m}-th line contains the description of the \textbf{m}-th (\textbf{1 }≤ \textbf{ m }≤ \textbf{21}) fold.
\OutputFile
Output consists of exactly \textbf{1024 }lines. The \textbf{m}-th line (\textbf{1 }≤ \textbf{m }≤ \textbf{1024}) contains the \textbf{m}-th number from top.
Sample data are too big to show on paper, but if \textbf{k} = \textbf{3} and you have to output the first \textbf{5} numbers, the output is the following:
Входные данные #1
LU RD RU LU LD RU RU LU LU LD LU LD RD RD LU RD LD RD RD RU RU
Выходные данные #1
76074 2021079 1124650 972503 600362 1496791 1648938 448215 338218 1758935 1386794 710359 862506 1234647 1911082 186071 207146 1890007 1255722 841431 731434 1365719 1780010 317143 469290 1627863 1517866 579287 993578 1103575 2042154 54999 10538 2086615 1059114 1038039 534826 1562327 1583402 513751 272682 1824471 1321258 775895 796970 1300183 1845546 251607 141610 1955543 1190186 906967 665898 1431255 1714474 382679 403754 1693399 1452330 644823 928042 1169111 1976618 120535 108842 1988311 1157418 939735 633130 1464023 1681706 415447 370986 1726167 1419562 677591 895274 1201879 1943850 153303 239914 1857239 1288490 808663 764202 1332951 1812778 284375 502058 1595095 1550634 546519 1026346 1070807 2074922 22231 43306 2053847 1091882 1005271 567594 1529559 1616170 480983 305450 1791703 1354026 743127 829738 1267415 1878314 218839 174378 1922775 1222954 874199 698666 1398487 1747242 349911 436522 1660631 1485098 612055 960810 1136343 2009386 87767 92458 2004695 1141034 956119 616746 1480407 ...