Как известно, английский математик Фрэнк Грей (Franc Gray) предложил остроумную формулу, которая позволяет по порядковому номеру определить соответствующий член последовательности, обладающей тем свойством, что двоичное представление каждого последующего члена отличается ровно в одном от двоичного представления предыдущего. Если обозначить \textbf{i}-ый разряд двоичного представления порядкового номера кода Грея через \textbf{N_i}, а через \textbf{G_i} - \textbf{i}-ый разряд двоичного представления соответствующего кода Грея, то имеет место формула: \textbf{G_i} = \textbf{N_i^N_\{i+1\}} Отметим, что разряды считаются занумерованными справа налево (с нуля). Функция на языке C, реализующая получение кода Грея для заданного целого параметра, равному номеру этого кода будет выглядеть так: \textit{\textbf{unsigned long long G(long long N)}} \textit{\textbf{\{ return V ^ V >> 1;\}}} Последовательность (\textbf{G_i}) будем называть последовательностью Грея. Наша задача, по заданному коду Грея получить число, которому этот код соответствует (т.е. номер члена последовательности Грея, равного этому коду). \InputFile Файл состоит из единственной строки - кода Грея, заданного в шестнадцатиричном виде. Длина заданной строки не превосходит \textbf{200 000}, в качестве цифр, значения которых превосходят \textbf{9}, взяты первые английские буквы верхнего регистра. \OutputFile Выходной файл состоит из единственной строки - шестнадцатиричного значения числа, код Грея которого был задан во входном файле. У результата не должно быть ведущих нулей, в качестве цифр, значения которых превосходят \textbf{9}, следует взять первые английские буквы верхнего регистра.