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