종이띠 접기

면접 대비

시간 제한1초메모리 제한256 MB

요약

주어진 K번의 절반 접기를 차례로 시뮬레이션하고 2^K개 칸 번호를 위에서 아래로 출력합니다.

문제

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

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

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

$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$ 번째에 있는 칸의 번호를 출력한다.