The Robot Mower's Folded Walk

A robot mower covers a square lawn of 2**n by 2**n cells, visiting each cell exactly once and moving to a side-neighbour at every step. Cells are (x, y): x is the column counted from the left, y the row counted from the bottom, both starting at 0.

The walk of order n is defined recursively. Order 0 is the single cell (0, 0). For n >= 1, let h = 2**(n - 1). The mower walks the four h-by-h quarters in this order, each time following the order n - 1 walk moved into place as shown, where (a, b) is a cell of the smaller walk:

1. lower-left: (a, b) goes to (b, a) (mirrored across the diagonal)
2. upper-left: (a, b) goes to (a, b + h)
3. upper-right: (a, b) goes to (a + h, b + h)
4. lower-right: (a, b) goes to (2*h - 1 - b, h - 1 - a)

Write mower_step(n, x, y) returning the step (starting at 0) on which cell (x, y) is mown.

Examples

Input:  n = 1, x = 1, y = 0
Output: 3
Explanation: the order 1 walk is (0,0), (0,1), (1,1), (1,0).

Input:  n = 2, x = 2, y = 1
Output: 13
Explanation: the order 2 walk is
(0,0) (1,0) (1,1) (0,1) (0,2) (0,3) (1,3) (1,2)
(2,2) (2,3) (3,3) (3,2) (3,1) (2,1) (2,0) (3,0)

Constraints

• 0 <= n <= 30, 0 <= x, y < 2**n
• The walk has up to 2**60 cells, so it cannot be built.

Goals

• Find which quarter of the field a cell lies in and how many steps come before that quarter
• Undo the mirror applied to a quarter so the cell can be located in the smaller walk
• Answer for a field of 2**30 by 2**30 cells without building the walk