Under construction

Still being built. Things may change

Thue-Morse String

Interview

Time limit1sMemory limit256 MB

Summary
Find the character at position k in the Thue-Morse sequence, where k can be as large as 10^18.
Level

Easy3 of 10

Topics
Bit manipulation, Math, Recursion
Solved
No attempts yet

Problem

There is an infinite string X made of 0s and 1s. It is built as follows.

  1. X starts as "0".
  2. Form the string X' by swapping every 0 in X to 1 and every 1 to 0.
  3. Redefine X as the string obtained by appending X' to the end of X.
  4. Repeat steps 2 and 3 forever.

So X starts as "0", then becomes "01", then "0110", then "01101001", and so on, giving

"011010011001011010010110011010011001011001101001⋯⋯"

Given a positive integer k, find which character stands at position k of X.

Input

The first line gives the positive integer k (1 ≤ k ≤ 10^18).

Output

Print the character at position k on the first line.

Examples3

  1. Example 1

    Input
    1
    Expected output
    0

  2. Example 2

    Input
    2
    Expected output
    1

  3. Example 3

    Input
    10
    Expected output
    0