Z
한 변의 길이가 2^N인 정사각형 모양의 2차원 배열이 있다.
즉, 배열의 전체 크기는 2^N × 2^N이다.
이 배열의 모든 칸은 정해진 규칙에 따라 차례대로 방문된다.
가장 작은 기본 단위인 2×2 배열에서는 다음 순서로 칸을 방문한다.
- 왼쪽 위 칸
- 오른쪽 위 칸
- 왼쪽 아래 칸
- 오른쪽 아래 칸
이 네 칸을 순서대로 이어 보면 알파벳 Z와 같은 모양이 된다.
배열의 크기가 2×2보다 큰 경우에는, 현재 배열을 같은 크기의 네 영역으로 나눈다.
그 후 다음 순서로 각 영역을 방문한다.
- 왼쪽 위 영역
- 오른쪽 위 영역
- 왼쪽 아래 영역
- 오른쪽 아래 영역
각 영역 안에서도 다시 같은 규칙을 적용하여 재귀적으로 방문 순서가 정해진다.
정수 N과 찾고자 하는 칸의 위치 r, c가 주어진다.
행과 열의 번호는 모두 0부터 시작한다.
이때 r행 c열의 칸이 전체 배열을 Z 모양 순서로 방문할 때 몇 번째로 방문되는지 구하시오.
방문 순서는 0번째부터 시작한다.
입력
첫째 줄에 정수 N, r, c가 주어진다.
출력
r행 c열을 몇 번째로 방문했는지 출력한다.
제한
- 1 ≤ N ≤ 15
- 0 ≤ r, c < 2^N
예제 입력 1
2 3 1
예제 출력 1
11
예제 입력 2
3 7 7
예제 출력 2
63
예제 입력 3
1 0 0
예제 출력 3
0
예제 입력 4
4 7 7
예제 출력 4
63
예제 입력 5
10 511 511
예제 출력 5
262143
예제 입력 6
10 512 512
예제 출력 6
786432