AntiGray
The English mathematician Frank Gray introduced an intriguing formula for determining the sequence member corresponding to a given ordinal number. This sequence has the characteristic that each successive member's binary representation differs by exactly one bit from the previous member's. If we denote the i-th bit of the binary representation of the ordinal number in the Gray code as N_i, and G_i as the i-th bit of the binary representation of the corresponding Gray code, the formula is:
G_i = N_i^N_{i+1}
Note that the bits are numbered from right to left, starting at zero. In C language, the function that computes the Gray code for a given integer, representing the ordinal number of this code, is implemented as follows:
unsigned long long G(long long N)
{ return N ^ N » 1;}
The sequence (G_i) is referred to as the Gray sequence. Our task is to find the ordinal number corresponding to a given Gray code (i.e., the sequence member's ordinal number that matches this code).
Input
The input consists of a single line containing the Gray code in hexadecimal form. The length of this line does not exceed 200,000 characters, and for digits greater than 9, uppercase English letters are used.
Output
The output should be a single line containing the hexadecimal value of the number whose Gray code was provided in the input. The result should not include leading zeros, and for digits greater than 9, uppercase English letters should be used.