Z

Interview

Time limit0.5sMemory limit512 MB

Summary

Given N and coordinates (r,c) in a 2^N x 2^N grid, compute the visit order index of that cell under recursive Z-order (Morton order) traversal.

Level: Easy3 of 10
Topics: Divide and conquer, Recursion, Bit manipulation
Solved: No attempts yet

Problem

A square array of size 2^N x 2^N is visited in Z-order. In a 2 x 2 array, the cells are visited in this order: upper-left, upper-right, lower-left, lower-right. This order forms a Z shape.

When N > 1, divide the array into four subarrays of size 2^(N-1) x 2^(N-1), then visit those subarrays recursively in the same order: upper-left, upper-right, lower-left, lower-right.

The following figure shows the visit order for an array of size 2^2 x 2^2.

Given N, r, and c, write a program that outputs when the cell at row r and column c is visited.

The following figure shows the visit order when N = 3.

Input

The first line contains three integers N, r, and c.

Output

Print the visit order of the cell at row r and column c.

Constraints

1 <= N <= 15
0 <= r, c < 2^N

Examples6

Example 1
Input
```
2 3 1
```
Expected output
```
11
```
Example 2
Input
```
3 7 7
```
Expected output
```
63
```
Example 3
Input
```
1 0 0
```
Expected output
```
0
```
Example 4
Input
```
4 7 7
```
Expected output
```
63
```
Example 5
Input
```
10 511 511
```
Expected output
```
262143
```
Example 6
Input
```
10 512 512
```
Expected output
```
786432
```