Gray's Code
Gray codes are named after Frank Gray, a physicist from Bell Telephone Laboratories. In the 1930s, he developed a method that is still used today for transmitting color television signals. This method allows a color signal to be displayed in shades of gray when received by a black-and-white receiver.
There are various types of Gray codes, but we'll focus on one specific type: the "binary reflected Gray code." This is the standard Gray code referred to when no specific type is mentioned.
The binary reflected Gray code is constructed as follows: We begin with the sequences 0 and 1, representing the integers 0 and 1, respectively.
Next, we reflect these sequences across the horizontal axis and prepend a 1 to the new entries, while prepending a 0 to the existing entries.
This process yields the reflected Gray code for n = 2. To generate the code for n = 3, we repeat the procedure:
Using this construction method, we can observe by induction on n that: first, each of the 2^n bit combinations appears exactly once in the list; second, transitioning from one list element to the next involves changing only one bit; and third, transitioning from the last list element back to the first also involves changing only one bit. Gray codes with this last property are termed cyclic, and the reflected Gray code is inherently cyclic.
For each given number k, you need to output the decimal value of the k-th Gray code.
Input
The input consists of multiple test cases, each containing a single number k (0 ≤ k ≤ 10^18) on a separate line. The total number of test cases does not exceed 10^5.
Output
For each number k provided, output the decimal value of the k-th Gray code on a separate line.