종이띠 접기

양의 정수 $K$에 대해 칸이 $N = 2^K$개인 종이띠가 있다. 칸에는 왼쪽부터 오른쪽으로 $1$번부터 $N$번까지 번호가 붙어 있다. 아래 그림은 $K = 3$, 즉 $N = 8$인 종이띠를 옆에서 본 모습이다. 위에서 본 모습이 아니다.

종이띠는 절반으로 접을 수 있다. 한가운데에 접는 선을 표시하고 한쪽 절반은 그대로 둔 채 나머지 절반을 위나 아래로 넘긴다. 접는 방법은 네 가지다.

• LU: 왼쪽 절반을 위로 넘겨 오른쪽 절반 위에 올린다.
• LD: 왼쪽 절반을 아래로 넘겨 오른쪽 절반 밑에 넣는다.
• RU: 오른쪽 절반을 위로 넘겨 왼쪽 절반 위에 올린다.
• RD: 오른쪽 절반을 아래로 넘겨 왼쪽 절반 밑에 넣는다.

넘어가는 절반은 뒤집힌다. 그 절반의 칸은 좌우가 뒤바뀐 순서로 놓이고, 층도 위아래가 뒤집힌 순서로 놓인다.

$K$번 접고 나면 종이띠는 폭이 한 칸, 두께가 $N$층이 된다. $K = 3$인 종이띠를 RU, LD, LU 순서로 세 번 접어 보자. 한 번 접을 때마다 모습은 다음과 같다.

위에서 아래로 읽으면 칸이 $7, 2, 3, 6, 5, 4, 1, 8$ 순서로 놓여 있다.

접는 순서가 주어지면 다 접은 종이띠의 칸을 위에서 아래로 구하는 프로그램을 작성하시오.

입력은 $K$줄이고 한 줄에 접기 한 번이 주어진다. $M$번째 줄에는 $M$번째로 접는 방법이 LU, LD, RU, RD 중 하나로 두 글자 주어진다. 접기는 주어진 순서대로 수행한다.

$1 \le K \le 10$이고, 종이띠의 칸 수는 $N = 2^K$이다.

$2^K$줄을 출력한다. $M$번째 줄에는 다 접은 종이띠에서 위로부터 $M$번째에 있는 칸의 번호를 출력한다.