Folding a Paper Stripe

A paper stripe has $N = 2^K$ cells for a positive integer $K$. The cells are numbered $1$ to $N$ from left to right. The picture below is a side view of the stripe for $K = 3$, so $N = 8$. It is a side view, not a top view.

You may fold the stripe in half. Mark it at the center, keep one half where it lies, and turn the other half over onto it, either up or down. That gives four folds:

• LU: the left half turns up, onto the top of the right half.
• LD: the left half turns down, under the right half.
• RU: the right half turns up, onto the top of the left half.
• RD: the right half turns down, under the left half.

The half that moves is turned over. Its cells end up in mirrored left to right order, and its layers end up in the opposite top to bottom order.

After $K$ folds the stripe is one cell wide and $N$ layers thick. Take the stripe with $K = 3$ and fold it three times, first RU, then LD, then LU. Here is the stripe after each fold:

Read from top to bottom, the cells are now $7, 2, 3, 6, 5, 4, 1, 8$.

Given the folds, report the cells of the folded stripe from top to bottom.

The input has $K$ lines, one per fold. Line $M$ holds the $M$-th fold as two letters: LU, LD, RU, or RD. The folds are applied in the order given.

$1 \le K \le 10$, and the stripe has $N = 2^K$ cells.

Print $2^K$ lines. Line $M$ holds the number of the cell that lies $M$-th from the top of the folded stripe.