output_description: Print the base -2 representation of N.
  
  * * *
input_description: Input is given from Standard Input in the following format:
  
      
      
      N
attempt: n = int(input())
  if n == 0:
      print(0)
      exit(0)
  
  oddsum = [
      2,
      10,
      42,
      170,
      682,
      2730,
      10922,
      43690,
      174762,
      699050,
      2796202,
      11184810,
      44739242,
      178956970,
      715827882,
      2863311530,
  ]
  evensum = [
      1,
      5,
      21,
      85,
      341,
      1365,
      5461,
      21845,
      87381,
      349525,
      1398101,
      5592405,
      22369621,
      89478485,
      357913941,
      1431655765,
  ]
  two = [
      1,
      2,
      4,
      8,
      16,
      32,
      64,
      128,
      256,
      512,
      1024,
      2048,
      4096,
      8192,
      16384,
      32768,
      65536,
      131072,
      262144,
      524288,
      1048576,
      2097152,
      4194304,
      8388608,
      16777216,
      33554432,
      67108864,
      134217728,
      268435456,
      536870912,
      1073741824,
      2147483648,
      4294967296,
      8589934592,
      17179869184,
  ]
  ans = 0
  while n != 0:
      if n < 0:
          x = 1
          for i in oddsum:
              if n >= -1 * i:
                  break
              x += 2
          n += two[x]
      else:
          x = 0
          for i in evensum:
              if n <= i:
                  break
              x += 2
          n -= two[x]
      v = 1 << x
      ans += v
  print(bin(ans))
  
problem_description: Statement
  
  Given an integer N, find the base -2 representation of N.
  
  Here, S is the base -2 representation of N when the following are all
  satisfied:
  
    * S is a string consisting of `0` and `1`.
    * Unless S = `0`, the initial character of S is `1`.
    * Let S = S_k S_{k-1} ... S_0, then S_0 \times (-2)^0 + S_1 \times (-2)^1 + ... + S_k \times (-2)^k = N.
  
  It can be proved that, for any integer M, the base -2 representation of M is
  uniquely determined.
samples: [{"input": "-9", "output": "1011\n    \n\nAs (-2)^0 + (-2)^1 + (-2)^3 = 1 + (-2) + (-8) = -9, `1011` is the base -2\nrepresentation of -9.\n\n* * *"}, {"input": "123456789", "output": "11000101011001101110100010101\n    \n\n* * *"}, {"input": "0", "output": "0"}]