Stripe
Stripe
Let k be some positive integer. We have a paper stripe with n = 2^k cells. Cells are numbered left to right with numbers from 1 to n. Here is how the stripe looks like initially (this is a side view, not a top view!) for k = 3, and correspondingly, n = 8:
1 2 3 4 5 6 7 8
We can fold the stripe in the following way: stripe is marked in its center and, keeping one half not touched, fold the other up or down. First, we fold right half up. Then, we fold left half down, and finally, we fold left half up. This is how sample stripe will look like after each move:
As we see, numbers on the stripe from top to bottom stand in the following order: 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.
Giriş verilənləri
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.
Çıxış verilənləri
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:
Nümunə
LU RD RU LU LD RU RU LU LU LD LU LD RD RD LU RD LD RD RD RU RU
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 ...