Робот Гильберта

Кривая Гильберта порядка N – самоподобная непрерывная ломаная, заполняющая квадрат 2^N x 2^N и проходящая через все клетки данного квадрата. Каждая кривая N-го порядка строится рекурсивно: квадрат делится на 4 части и в каждой из частей рисуется кривая (N-1)-го порядка. При этом верхние части остаются без изменений, а нижние поворачиваются на 90 градусов в разные стороны. Далее, все части соединяются тремя отрезками, образуя непрерывную ломаную.

На следующем рисунке показаны первые три кривые:

Робот начал свое движение по кривой Гильберта из клетки с координатами (1,1) и в некоторый момент остановился в клетке с координатами (X,Y). Ваша задача – определить количество шагов, которые он сделал, чтобы попасть в данную клетку. За шаг следует считать перемещение в соседнюю клетку.

Входные данные

Входной файл INPUT.TXT содержит натуральные числа N, X и Y (N ≤ 30, X,Y ≤ 2^N). Здесь N – порядок кривой Гильберта, (X,Y) – координата робота.

Выходные данные

В выходной файл OUTPUT.TXT выведите ответ на задачу.

Примеры

Система оценки

Решения, работающие только для N ≤ 3, будут оцениваться в 20 баллов.

Решения, работающие только для N ≤ 10, будут оцениваться в 70 баллов.

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!