Paper Folding

There are four ways to fold a square sheet of paper along its center lines, as the figures below show.

• D: fold in half along the horizontal center line so that the top face covers the bottom face.

• U: fold in half along the horizontal center line so that the bottom face covers the top face.

• R: fold in half along the vertical center line so that the left face covers the right face.

• L: fold in half along the vertical center line so that the right face covers the left face.

Given a square sheet whose side length is $2^k$, folding it $k$ times vertically and $k$ times horizontally (the order does not matter) yields a square whose side length is 1. Punch a hole at one of the four corners of this unit square, as the figure below shows. The hole positions are labeled with numbers as in the figure.

After punching the hole, unfold the paper in the reverse of the folding order, and the paper has $2^{2k}$ holes. For example, fold a square with side length $4(= 2^2)$ in the order <R, D, D, R>, punch a hole at position 3, and unfold the paper; the holes appear as in the figure below.

Given an integer $k$ giving the paper size, the folding order, and the hole position, write a program that prints the positions of the holes in the $2^k \times 2^k$ grid.

The first line gives $k$.

The second line gives $2k$ characters representing the folding methods, separated by spaces. The folding methods D, U, R, L are given as the corresponding uppercase letters.

The third line gives the integer $h(0 \le h \le 3)$ representing the hole position.

Unfold the folded paper in the reverse of the folding order, then print the positions of the holes in the square as numbers. The output consists of $2^k$ lines; line $i(1 \le i \le 2^k)$ gives the numbers of the holes in row $i$ of the grid from left to right, separated by spaces.

• $1 \le k \le 8$
• The paper is folded exactly $k$ times horizontally and $k$ times vertically.