Коды Грея получили своё название по имени Франка Грея (Frank Gray), физика из Bell Telephone Laboratories, который в 1930-х годах изобрёл метод, в настоящее время используемый для передачи цветного телевизионного сигнала, совместно с существующими методами передачи и получения чёрно-белого сигнала; т.е. при получении цветного сигнала чёрно-белым приёмником изображение выводится оттенками серого цвета.
Хотя существует множество различных вариантов кодов Грея, рассмотрим только один: "двоичный отражённый (рефлексный) код Грея". Именно этот код обычно имеется в виду, когда говорят о неконкретном "коде Грея".
Отображённый двоичный код Грея строится следующим образом. Начинаем со строк 0 и 1, которые представляют соответственно целые числа 0 и 1.
Возьмём отражение этих строк относительно горизонтальной оси после приведённого списка и поместим 1 слева от новых записей списка, а слева от уже имевшихся разместим 0.
Таким образом получен отражённый код Грея для n = 2. Чтобы получить код для n = 3, повторим описанную процедуру и получим:
При таком способе построения легко увидеть по индукции по n, что, во-первых, каждая из 2^n комбинаций битов появляется в списке, причём только один раз; во-вторых, при переходе от одного элемента списка к рядом стоящему изменяется только один бит; в-третьих, только один бит изменяется при переходе от последнего элемента списка к первому. Коды Грея, обладающие последним свойством называются циклическими, и отражённый код Грея обязательно является таковым.
Для каждого заданного числа k вывести десятичное значение k-го кода Грея.
Во входном файле содержится некоторый набор тестовых данных, каждое число k (0 ≤ k ≤ 10^18) в наборе задано в отдельной строке. Количество наборов данных в одном тесте не превышает 10^5.
Для каждого заданного числа k вывести в отдельной строке десятичное значение k-го кода Грея.