종이접기

정사각형 종이를 중심선을 따라 접는 방법은 아래 그림처럼 4가지가 있다.

• D: 가로 중심선을 따라 반으로 접되 윗면이 아랫면을 덮도록 접는다.

• U: 가로 중심선을 따라 반으로 접되 아랫면이 윗면을 덮도록 접는다.

• R: 세로 중심선을 따라 반으로 접되 왼쪽 면이 오른쪽 면을 덮도록 접는다.

• L: 세로 중심선을 따라 반으로 접되 오른쪽 면이 왼쪽 면을 덮도록 접는다.

한 변의 길이가 $2^k$인 정사각형 종이를 세로로 $k$번, 가로로 $k$번 접으면 (접는 순서는 상관없다) 각 변의 길이가 1인 정사각형이 된다. 아래 그림처럼 각 변의 길이가 1인 정사각형의 네 귀퉁이 중 한 곳에 구멍을 낸다. 구멍의 위치는 그림처럼 숫자로 나타낸다.

구멍을 낸 뒤 접은 순서의 역순으로 종이를 펼치면 종이에는 $2^{2k}$개의 구멍이 생긴다. 예를 들어 한 변의 길이가 $4(= 2^2)$인 정사각형을 <R, D, D, R> 순서로 접은 뒤 3번 위치에 구멍을 내고 종이를 펼치면 아래 그림처럼 구멍이 생긴다.

종이의 크기를 나타내는 정수 $k$, 종이를 접는 순서, 구멍을 내는 위치가 주어질 때 $2^k \times 2^k$ 격자에 뚫린 구멍의 위치를 출력하는 프로그램을 작성하시오.

첫째 줄에 $k$가 주어진다.

둘째 줄에 종이를 접는 방법을 나타내는 문자가 $2k$개 주어지며, 각 문자는 공백으로 구분된다. 접는 방법 D, U, R, L은 각각 해당하는 대문자 알파벳으로 주어진다.

셋째 줄에 구멍을 내는 위치를 나타내는 정수 $h(0 \le h \le 3)$가 주어진다.

접힌 종이를 접은 순서의 역순으로 펼친 뒤 정사각형에 뚫린 구멍의 위치를 번호로 출력한다. 출력은 모두 $2^k$줄이며, $i(1 \le i \le 2^k)$번째 줄에는 격자의 $i$번째 행에 뚫린 구멍의 번호를 왼쪽에서 오른쪽 순서로 공백을 사이에 두고 출력한다.

• $1 \le k \le 8$
• 반드시 가로로 $k$번, 세로로 $k$번 접는다.