eolymp
bolt
Try our new interface for solving problems
Problems

Stripe

Stripe

Time limit 0.5 seconds
Memory limit 256 MiB

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.

Input data

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 data

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:

Examples

Input example #1
LU
RD
RU
LU
LD
RU
RU
LU
LU
LD
LU
LD
RD
RD
LU
RD
LD
RD
RD
RU
RU
Output example #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
...
Source ACM ICPC SEERC-2012, 13.10.2012 Bucharest, Vinnica