AntiGray#725
As is known, the English mathematician Frank Gray introduced a clever formula that allows one to determine, given a sequence number, the corresponding member of a sequence where the binary representation of each subsequent member differs from the previous one by exactly one bit. If we denote the -th bit of the binary representation of the ordinal number in the Gray code as N_i, and G_i as the -th bit of the binary representation of the corresponding Gray code, the formula is:
Note that the bits are numbered from right to left, starting from zero. In C, the function that returns the Gray code for a given integer parameter equal to the number is as follows:
unsigned long long G(long long N)
{ return N ^ (N 1);}
We call the sequence (G_i) the Gray sequence. The task is: given a Gray code, obtain the number for which this is the Gray code (i.e., the ordinal number of the member of the Gray sequence equal to this code).
The file contains a single line — the Gray code given in hexadecimal form. The length of the input does not exceed . For digits with values greater than , the first uppercase English letters are used.
The output consists of a single line — the hexadecimal value of the number whose Gray code was given in the input file. The output should have no leading zeros. For digits greater than , uppercase English letters are used.
Example 1