정사각형의 종이를 중앙선을 중심으로 접는 방법은 아래 그림에서 보인 것처럼 4가지가 있다.

한 변의 길이가 2^k인 정사각형 종이가 있을 때, 이를 세로로 k번, 가로로 k번 접으면 (접는 순서는 상관없음) 각 변의 길이가 1인 정사각형이 된다.

아래 그림에서 보인 것처럼 각 변의 길이가 1인 정사각형의 네 귀퉁이 중 한 군데에 구멍을 낸다.

구멍의 위치는 그림에서 보인 것처럼 숫자로 표시한다.

구멍을 낸 후 접은 순서의 역순으로 종이를 펼치면, 종이에 2^2k개의 구멍이 있게 된다.

예를 들어, 한 변의 길이가 4(= 2²)인 정사각형을 <R, D, D, R> 순서대로 접은 후, 3번 위치에 구멍을 낸 다음 종이를 펼치면 아래 그림처럼 구멍이 나게 된다.

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

[제약 조건]

종이접기 timer 1s memory 64MB

종이접기 1s 64MB