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())
  p = []
  if N > 0:
      for i in range(500):
          if (2 ** (2 * i) - 1) / 3 < N <= (2 ** (2 * (i + 1)) - 1) / 3:
              q = 2 * i + 1
  if N < 0:
      for i in range(1, 500):
          if -(2 ** (2 * i + 1) - 2) / 3 <= N < -(2 ** (2 * i - 1) - 2) / 3:
              q = 2 * i
  if N == 0:
      q = 1
  
  
  def cal(n, i):
      if i % 2 != 0:
          if (2 ** (i - 1) - 1) / 3 < n <= (2 ** (i + 1) - 1) / 3:
              p.append(1)
              n = n - (-2) ** (i - 1)
              i = i - 1
              if i > 0:
                  cal(n, i)
          else:
              p.append(0)
              i = i - 1
              if i > 0:
                  cal(n, i)
      elif n == 0:
          p.append(0)
          i = i - 1
          if i > 0:
              cal(n, i)
      else:
          if -(2 ** (i + 1) - 2) / 3 <= n < -(2 ** (i - 1) - 2) / 3:
              p.append(1)
              n = n - (-2) ** (i - 1)
              i = i - 1
              if i > 0:
                  cal(n, i)
          else:
              p.append(0)
              i = i - 1
              if i > 0:
                  cal(n, i)
  
      return p
  
  
  ans = cal(N, q)
  for i in range(len(ans)):
      ans[i] = str(ans[i])
  print(int("".join(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"}]