eolymp
bolt
Try our new interface for solving problems
Problems

Коды Грея

Коды Грея

Time limit 1 second
Memory limit 64 MiB

Коды Грея получили своё название по имени Франка Грея (Frank Gray), физика из Bell Telephone Laboratories, который в 1930-х годах изобрёл метод, в настоящее время используемый для передачи цветного телевизионного сигнала, совместно с существующими методами передачи и получения чёрно-белого сигнала; т.е. при получении цветного сигнала чёрно-белым приёмником изображение выводится оттенками серого цвета.

Хотя существует множество различных вариантов кодов Грея, рассмотрим только один: "двоичный отражённый (рефлексный) код Грея". Именно этот код обычно имеется в виду, когда говорят о неконкретном "коде Грея".

Отображённый двоичный код Грея строится следующим образом. Начинаем со строк 0 и 1, которые представляют соответственно целые числа 0 и 1.

Возьмём отражение этих строк относительно горизонтальной оси после приведённого списка и поместим 1 слева от новых записей списка, а слева от уже имевшихся разместим 0.

Таким образом получен отражённый код Грея для n = 2. Чтобы получить код для n = 3, повторим описанную процедуру и получим:

При таком способе построения легко увидеть по индукции по n, что, во-первых, каждая из 2^n комбинаций битов появляется в списке, причём только один раз; во-вторых, при переходе от одного элемента списка к рядом стоящему изменяется только один бит; в-третьих, только один бит изменяется при переходе от последнего элемента списка к первому. Коды Грея, обладающие последним свойством называются циклическими, и отражённый код Грея обязательно является таковым.

Для каждого заданного числа k вывести десятичное значение k-го кода Грея.

Input data

Во входном файле содержится некоторый набор тестовых данных, каждое число k (0k10^18) в наборе задано в отдельной строке. Количество наборов данных в одном тесте не превышает 10^5.

Output data

Для каждого заданного числа k вывести в отдельной строке десятичное значение k-го кода Грея.

Examples

Input example #1
3
14
5
12
Output example #1
2
9
7
10