Z Order Traversal

In video encoding, it is common to partition a frame of video into blocks, where the image is represented as a $2^n \times 2^n$ grid. Two common traversal orders are used: the normal raster scan (from left to right, top to bottom) and the Z-order traversal. In this problem, you are given the grid size exponent n and the coordinates (r, c) of a cell. Your task is to determine the order in which the cell is visited in a Z-shaped traversal, which is recursively defined as follows:

1. For a $2^0 \times 2^0$ grid, visit the only cell.
2. For a $2^k \times 2^k$ grid (k > 0), split the grid into 4 equal parts by dividing it in the middle both horizontally and vertically. The 4 sub-grids are visited in the order: top-left, top-right, bottom-left, bottom-right.

For example, consider a $4 \times 4$ grid (when n = 2):

• The top-left quadrant corresponds to cells (0, 0) to (1, 1).
• The top-right quadrant corresponds to cells (0, 2) to (1, 3).
• The bottom-left quadrant corresponds to cells (2, 0) to (3, 1).
• The bottom-right quadrant corresponds to cells (2, 2) to (3, 3).

Your task is to compute the visit order of the cell (r, c) given the grid size determined by n where the overall grid dimensions are $2^n \times 2^n$. The order is 0-indexed (i.e. the first cell visited is numbered 0).

inputFormat

The input consists of a single line containing three non-negative integers separated by spaces:

• n: the exponent determining the grid size ($2^n \times 2^n$).
• r and c: the row and column indices of the cell.

Note: It is guaranteed that 0 ≤ r, c < 2^n.

outputFormat

Output a single integer representing the order in which the cell (r, c) is visited during the Z-shaped traversal.

sample

0 0 0

0