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.

-----Constraints-----
 - Every value in input is integer.
 - -10^9 \leq N \leq 10^9

-----Input-----
Input is given from Standard Input in the following format:
N

-----Output-----
Print the base -2 representation of N.

-----Sample Input-----
-9

-----Sample Output-----
1011

As (-2)^0 + (-2)^1 + (-2)^3 = 1 + (-2) + (-8) = -9, 1011 is the base -2 representation of -9.

Difficulty: introductory

Starter code:

Solutions:
from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf,comb
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

n = INT()

if n == 0:
    print(0)
    return

ans = deque()
i = 0
while n != 0:
    tmp = ( n % 2**(i+1) ) // 2**i
    ans.appendleft(tmp)
    n -= tmp * (-2)**i
    i += 1
print(*list(ans),sep="")

N = int(input())

s = ""

while N != 0:
    # Pythonでは負の数を割っても余りが正になる
    # -2で割ったときの"理想的な"余り(0or1になってくれる)は2で割った余りと同じ
    r = int(N % 2)
    # ここは-2
    N = (N - r) / (-2)
    s += str(int(r))

# N=0の時はから文字列が返ってきてしまう
if s == "":
    print((0))
    return
else:
    # reverse
    print((s[::-1]))


n = int(input())
#a, b = map(int,input().split())
#l = list(map(int,input().split()))
#l = [list(map(int,input().split())) for i in range(n)]

ansl = []
if n != 0:
    while abs(n) > 0:
        if n % 2 == 0:
            ansl.append("0")
            n = n//(-2)
        else:
            ansl.append("1")
            n = (n-1)//(-2)
    print((''.join(ansl[::-1])))
else:
    print((0))


import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, log2
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()

if N == 0:
	print(0)
	return

lim = 32
top = [0]*(lim+1)
bottom = [0]*(lim+1)

for i in range(1, lim+1):
	if i%2:
		t = (i+1)//2
		top[i] = (4**t-1)//3
		bottom[i] = bottom[i-1]
	else:
		b = i//2
		bottom[i] = (4**b-1)*2//3
		top[i] = top[i-1]

digit = [0]*(lim+1)
for i in range(1, lim+1):
	digit[i] = (-2)**(i-1)

if 0 <= N:
	idx = bisect_left(top, N)
else:
	idx = bisect_left(bottom, -N)

ans = ""
for i in range(idx, 0, -1):
	if -bottom[i-1] <= N <= top[i-1]:
		ans += "0"
	else:
		ans += "1"
		N -= digit[i]

print(ans)

N = int(input())

if N==0:
    print((0))
    return

ans = ''
while N:
    if N%2:
        N -= 1
        ans += '1'
    else:
        ans += '0'
    N //= -2

print((ans[::-1]))


N = int(input())

max_digit = 34

bits = [0]*max_digit
sign = N > 0
if N < 0: N = - N

for i in range(N.bit_length()):
    if (N >> i) & 1:
        if i & 1 == sign:
            bits[i] += 1
            bits[i + 1] += 1
        else:
            bits[i] += 1

for i in range(max_digit):
    if bits[i] == 2:
        if bits[i + 1] == 1:
            bits[i] = 0
            bits[i + 1] = 0
        else:
            bits[i] = 0
            bits[i + 1] += 1
            bits[i + 2] += 1

res = ''
flg = False
for i in reversed(range(max_digit)):
    if not flg and bits[i] == 1:
        flg = True
        res += '1'
    elif flg:
        res += str(bits[i])

if res == '': res = '0'

print(res)

n = int(input())

if n == 0:
    print(0)
    return

ans = []
while n != 0:
    ans.append(n % 2)
    n = - (n // 2)
print(''.join(map(str, reversed(ans))))

N = int(input())
if N == 0:
    s = '0'
else:
    s = ''
while N != 0:
    m = N%2
    s += str(m)
    N = (N - m)*(-1)//2
print(s[::-1])

n = int(input())

s = ''
while(n != 0):
    s = str(n % 2)+s
    n = -(n//2)
print((0 if(s == "") else s))


def mod(n):
    if n > 0:
        return -(n//2), n%2
    elif n < 0:
        return (-n+1)//2 ,(-n)%2
    else:
        return 0,0
    
def main():
    N = int( input())
    if N == 0:
        print((0))
        return
    ANS = []
    while N != 0:
        N, b = mod(N)
        ANS.append(b)
    print(("".join( map( str, ANS[::-1]))))
        
def __starting_point():
    main()

__starting_point()

N = int(input())
S = ""
while N!=0:
  if N&1:
    S = "1"+S
    N = (N-1)//(-2)
  else:
    S = "0"+S
    N = N//(-2)
print(0 if S=="" else S)

n=int(input())
if n==0:
    print(0)
    return
ans=""
while n!=0:
    r=n%-2
    if r<0:
        r+=2
    ans+=str(r)
    n=(n-r)//(-2)
print(ans[::-1])

N = int(input())
 
if N == 0:
    print(0)
    return
ans = []
while N:
    ans.append(N % 2)
    N = N // 2
    N *= -1
print("".join(map(str, ans[::-1])))

N = int(input())
def solve(N):
    if N == 0:
        return '0'
    ans = ''
    while N != 0:
        ans += str(N & 1)
        N >>= 1
        N *= -1
    return ans[::-1]
print(solve(N))

# 解説と以下を参考に作成
# https://atcoder.jp/contests/abc105/submissions/17007379
# import sys
# sys.setrecursionlimit(10 ** 6)
# import bisect
# from collections import deque
import math


# from decorator import stop_watch
#
#
# @stop_watch
def solve(N):
    if N == 0:
        print('0')
        return

    ans = ''
    while N != 0:
        # 1桁目が 1 or 0 かはNが奇数か偶数かによってのみ決まる.
        #  → 2 で割った余りから 1 or 0 を決定する.
        m = N % 2
        ans = str(m) + ans
        # 1桁目の情報を取り除いて(偶数にして)右シフトし, 次の桁についても同様に確認していく.
        # この時, 2(,4,6,...)桁目は負の要素となっているので, 1桁目(1 or 0)として判定するために正負を反転させる.
        N = (N - m) * (-1) >> 1
    print(ans)


def __starting_point():
    N = int(input())
    solve(N)

    # # test
    # from random import randint
    # from func import random_str
    # solve()

__starting_point()

import itertools
N = int(input())

if N == 0:
    print(0)
    return
ans = []
while N !=0:
    ans.append(N%2)
    N = -(N-N%2)//2
ans.reverse()
print("".join(list(map(str,ans))))

n = int(input())

s = ''
while True:
    if n % 2 == 0:
        s = '0' + s
        n = n // -2
    else:
        s = '1' + s
        n = (n - 1) // -2
    if n == 0:
        break
print(s)



N=int(input())
if N==0:
  print(0)
  return
if N>0:
  S=bin(N)[2:]
  S=list(S[::-1])
  S=list(map(int,S))
  S+=[0]*1000
  i=0
  while True:
    S[i+1]+=S[i]//2
    S[i]=S[i]%2
    if i%2==1:
      S[i+1]=S[i+1]+S[i]
    i+=1
    if i==len(S)-1:
      break
  S=list(map(str,S))
  S=list(reversed(S))
  S="".join(S)
  print(int(S))
else:
  N=abs(N)
  S=bin(N)[2:]
  S=list(S[::-1])
  S=list(map(int,S))
  S+=[0]*1000
  i=0
  while True:
    S[i+1]+=S[i]//2
    S[i]=S[i]%2
    if i%2==0:
      S[i+1]=S[i+1]+S[i]
    i+=1
    if i==len(S)-1:
      break
  S=list(map(str,S))
  S=list(reversed(S))
  S="".join(S)
  print(int(S))

n=int(input())
if n==0:
    print(0)
    return
ans=""
while n!=0:
    r=n%2
    ans+=str(r)
    n=(n-r)//(-2)
print(ans[::-1])

N = int(input())

ans = ""

if N == 0:
    print(0)
    return

while N != 0:
    a, b = divmod(N, 2)
    ans = str(b) + ans
    N = -a

print(ans)

s=""
n=int(input())
if n==0:print(0)
else:
 while n!=0:s=str(n%2)+s;n=-(n//2)
 print(s)

N  = int(input())
if N == 0:
    print((0))
else:
    ans = ""
    while N != 0:
        if N%2 == 1:
            ans += "1"
            N -= 1
        else:
            ans += "0"
        N //= -2
    print((ans[::-1]))
    # tmp = [1*(i==0) for i in ans][::-1]
    # print("".join(map(str, tmp)))


N=int(input())

if N >= 0:
  n = N
  i = 0
  while 1:
    b = bin(n)[2:]
    if i >= len(b):
      break
    if i % 2 == 1 and b[-i-1]=='1':
      n += 2**(i+1)
    i += 1
  print(bin(n)[2:])
  
else:
  n = -N
  i = 0
  while 1:
    b = bin(n)[2:]
    if i >= len(b):
      break
    if i % 2 == 0 and b[-i-1]=='1':
      n += 2**(i+1)
    i += 1
  print(bin(n)[2:])

#!/usr/bin/env python
# coding: utf-8

# In[6]:


N = int(input())


# In[7]:


a = ""
if N == 0:
    a = 0
while N != 0:
    if N%2 != 0:
        N -= 1
        a = "1" + a
    else:
        a = "0" + a
    N //= -2
print(a)


# In[ ]:






N = int(input())
ans = []
while N != 0:
    r = N % 2
    N = (N - r) // (-2)
    ans += [r]
print((''.join(map(str, ans[::-1])) if ans else 0))


def mod(i,j):
    if i%j == 0:
        return [str(0), i//j]
    else:
        return [str(-(i%j)),(i//j)+1]

n = int(input())
w = ""
if n == 0:
    w = 0
else:
    while n != 0:
        i,j = mod(n,-2)
        w = i + w
        n = j
print(w)

n=int(input())
if n==0:
    print(0)
    return
ans=""
while n!=0:
    r=n%2
    if r<0:
        r+=2
    ans+=str(r)
    n=(n-r)//(-2)
print(ans[::-1])

N=int(input())
ans=''
while 1:
    ans+=str(N%2)
    if N in [0,1]:
        break
    N=0-N//2
print(ans[::-1])

N = int(input())

def minus_binary(n, S: str):
    if n == 0:
        if S == "":
            S = "0"
        return S
    
    if n == 1:
        S = "1" + S
        return minus_binary(0, S)

    else:
        if n%2 == 1:
            n -= 1
            S = "1" + S
        else:
            S = "0" + S

        return minus_binary(n/(-2), S)

S = ""
print(minus_binary(N, S))

# -*- coding: utf-8 -*-
import sys
from collections import deque, defaultdict
from math import sqrt, factorial, gcd, ceil, atan, pi
# def input(): return sys.stdin.readline()[:-1] # warning not \n
# def input(): return sys.stdin.buffer.readline().strip() # warning bytes
# def input(): return sys.stdin.buffer.readline().decode('utf-8')
import string
# string.ascii_lowercase
from bisect import bisect_left
MOD = int(1e9)+7
INF = float('inf')


def solve():
    # n, m = [int(x) for x in input().split()]
    # n, m = [int(x) for x in input().split()]
    n = -int(input())
    if n == 0:
        print((0))
        return
    ans = []
    while n != 0:
        n, m = divmod(n, -2)
        ans.append(-m)

    ans.reverse()
    print((''.join([str(x) for x in ans])))

        


t = 1
# t = int(input())
for case in range(1,t+1):
    ans = solve()


"""

"""


#!/usr/bin/env python3

n = int(input())

if n == 0:
    print((0))
    return
ans = []
while(n != 0):

    rem = n % 2

    n = (n-rem)//(-2)

    ans.append(rem)

ans.reverse()

print(("".join(map(str, ans))))


N = int(input())
 
def base(x, n):
  ret = []
  while x != 0:
    ret.append( x % abs(n))
    if n < 0:
      x = - ( (-x)//n )
    else:
      x //= n
  return ret
 
if N == 0:
  print(0)
else:
  print("".join(map(str, reversed(base(N, -2)))))

N = int(input())
ans = []
if N == 0:
    print((0))
else:
    while N:
        ans.append(N % 2)
        N = -(N // 2)
    print(("".join(map(str, ans[::-1]))))


N = int(input())
if N == 0:
    s = '0'
else:
    s = ''
while N != 0:
    m = N%2
    s += str(m)
    N = (N - m)*(-1)//2
print(s[::-1])

N=int(input())
# 1011: -9
# 101  1 + 4 =5
# 10: -2
# 1

def calc(x):
    ans=""
    
    while True:

        if x%2==0:
            ans="0"+ans
        else:
            ans="1"+ans
            x-=1
        if x==0:
            break

        x = x//(-2)
    return ans

a=calc(N)

print(a)        

N = int(input())
if N == 0:
    print('0')
    return

ans = ''
while abs(N) > 0:
    if abs(N) % 2 == 0:
        ans += '0'
        N //= 2
    else:
        N -= 1
        N //= 2
        ans += '1'
    N *= -1
print((ans[::-1]))


import sys

input = sys.stdin.readline


def main():
    N = int(input())

    if N == 0:
        ans = "0"
    else:
        ans = ""
        while N != 0:
            q, r = divmod(N, -2)
            if r == 0:
                ans = "".join(["0", ans])
            else:
                ans = "".join(["1", ans])
            r = r + 2 if r < 0 else r
            N = (N - r) // -2

    print(ans)


def __starting_point():
    main()

__starting_point()

n = int(input())
if n == 0:
    print(0)
    return
d = []
while n != 0:
    p = n % 2
    d.append(p)
    n = (n - p) * (-1) // 2
for u in reversed(d):
    print(u, end='')
print()


n = int(input())
if n == 0:
  print(0)
  return
ans = []
while n>0 or n<0:
  if n == 0:
    break
  else:
    if n%2==0:
      ans.append(0)
      n = n//(-2)
    else:
      ans.append(1)
      n = (n-1)//(-2)
    
print(*ans[::-1], sep='')

def main():
    n = int(input())
    s = []
    if n==0:
        print((0))
        return
    while n!=1:
        if n%(-2)==-1:
            n = n//(-2)+1
            s.append(1)
        else:
            s.append(0)
            n = n//(-2)
    s.append(n)
    s.reverse()
    print((''.join([str(x) for x in s])))

def __starting_point():
    main()

__starting_point()

n = int(input())
N = n

ans = ""

while n != 0:
    if n % 2 == 1:
        ans += "1"
        n = n - 1
        n //= -2
    else:
        ans += "0"
        n //= -2

print(ans[::-1] if N != 0 else 0)

def main():
	import math
	N = int(input())
	n = math.ceil(math.log(100000000000, 4)) # toriaezu BIG ENOUGH na number
	M = int('10' * n, 2)
	B = format(N + M, 'b')
	print(even_toggle(B))

def even_toggle(b):
	r = []
	for i in range(len(b)):
		if i % 2 == 0:
			r.insert(0, b[-i-1])
		else:
			r.insert(0, str(1 - int(b[-i-1])))
	head_zeroes = 0
	for i in range(len(r)):
		if r[i] == "0":
			head_zeroes += 1
		else:
			break
	return "".join(r[head_zeroes:]) or "0"

main()

import math
import sys
pin=sys.stdin.readline

def main():
  N=int(pin())
  ansl=[]
  if N==0:
    print(0)
    return
  while True:
    if N==0:
      break
    ansl.append(N%2)
    N=-(N//2)
  ans="".join(map(str,ansl))
  ans=ans[::-1]
  print(ans)
  return
main()

N = int(input())
a = ""
if N == 0:
    a = 0
while N != 0:
    if N % 2 != 0:
        N -= 1
        a = "1" + a
    else:
        a = "0" + a
    N = N // -2
print(a)


import math
N = int(input())

ans = ""
if N == 1:
    print("1") 
elif N == 0:
    print("0")  
elif N == -1:
    print("10")
else:
    while True:
        r = N % 2
        N = (N-r) /-2
        ans = str(int(r)) + ans
        if N == 0 or N == 1:
            ans = str(int(N)) + ans
            break

    print(ans)

import math
N = int(input())
if N == 0:
  print(0)
  return
p = int(math.log2(abs(N))) + 1
ans = [0] * (p + 10)
now = 0
for i in range(p + 10):
  x = N % (2 ** (i + 1))
  y = (now + ((-1) ** i) * (2 ** i) ) % (2 ** (i + 1))
  if (y == x) or (y + 2 ** (i + 1) == x):
    now += ((-1) ** i) * (2 ** i)
    ans[i] = 1
  if now == N:
    break
  #print(now, ans, x, y)

#print("n", now, ans, x, y)
p = 0
for i in range(1, len(ans) + 1):
  if p == 0:
    if ans[-i] != 0:
      p = 1
      print(ans[-i], end = "")
  else:
    print(ans[-i], end = "")

print("")



#!/usr/bin/env python

n = int(input())

if n == 0:
    print((0))
    return

ans = ''
while abs(n) > 0:
    r = n%2 
    ans = str(r) + ans 
    
    if r == 1:
        n -= 1
    n //= (-2)

print(ans)


import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
def dp2(ini, i, j): return [[ini]*i for _ in range(j)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value
#from collections import Counter # a = Counter(A).most_common()
#from itertools import accumulate #list(accumulate(A))

N = ii()
ans = ''

def div(a, b=-2):
    if a >= 0:
        return -(a//(-b)), a%(-b)
    else:
        if (-a)%(-b) == 0:
            return (-a)//(-b), 0
        else:
            return (-a)//(-b)+1, 1

while True:
    N, m = div(N)
    ans += str(m)
    if abs(N) < 2:
        break

if N == -1:
    ans += '11'
elif N == 1:
    ans += '1'

print(ans[::-1])

N = int(input())
if N==0:
    print(0)
    return

ans = ''
while N!=1:
    d = N%2
    ans += str(d)
    N -= d
    N //= -2
ans += '1'
print(ans[::-1])

N=int(input())

b=-2
temp=N
ans=""
while True:
    if temp%b!=0:
        ans="1"+ans
        temp=temp-(b//(-2))
    else:
        ans="0"+ans
    b=b*(-2)
    if temp==0:break

print(ans)


# import sys
# sys.setrecursionlimit(10 ** 6)
# import bisect
# from collections import deque
import math
# from decorator import stop_watch
# 
# 
# @stop_watch
def solve(N):
    if N == 0:
        print('0')
        return
    x = math.ceil(math.log2(abs(N))) + 1
    minus = [(-2) ** i for i in range(1, x + 1, 2)]
    plus = [(-2) ** i for i in range(0, x + 1, 2)]
    minus.sort()
    plus.sort(reverse=True)

    minus_sum = [0]
    for m in minus:
        minus_sum.append(minus_sum[-1] + m)
    plus_sum = [0]
    for p in plus:
        plus_sum.append(plus_sum[-1] + p)

    ans = ''
    n = 0
    flg = True if len(plus) > len(minus) else False
    m = 0
    p = 0
    while True:
        if flg:
            tg = plus[p]
            p += 1
        else:
            tg = minus[m]
            m += 1

        if n + tg >= N:
            if n + tg != N and n + tg + (minus_sum[-1] - minus_sum[m]) > N:
                ans += '0'
            else:
                ans += '1'
                n += tg
        else:
            if n + tg + (plus_sum[-1] - plus_sum[p]) < N:
                ans += '0'
            else:
                ans += '1'
                n += tg
        flg = not flg
        if p >= len(plus) and m >= len(minus):
            break
    print((str(int(ans))))


def __starting_point():
    # S = input()
    N = int(input())
    # N, M = map(int, input().split())
    # A = [int(i) for i in input().split()]
    # B = [int(i) for i in input().split()]
    # AB = [[int(i) for i in input().split()] for _ in range(N)]
    solve(N)

    # # test
    # from random import randint
    # from func import random_str
    # solve()

__starting_point()

N = int(input())
a = 2
ans = ""
for i in range(1000):
    if N % a == 0:
        ans = "0"+ans
    else:
        ans = "1"+ans
        if i % 2 == 0:
            N -= 2**i
        else:
            N += 2**i
    a *= 2
    if N == 0:
        break
print(ans)


n=int(input())
x = ""
while n!=0:
    x = str(n%2) + x
    n = -(n//2)
if x == "":
    print((0))
else:
    print(x)


N = int(input())

if N == 0:
    print((0))
    return
ans = []
while N:
    ans.append(N % 2)
    N = N // 2
    N *= -1

print(("".join(map(str, ans[::-1]))))



import os
import sys
from collections import defaultdict, Counter
from itertools import product, permutations,combinations, accumulate
from operator import itemgetter
from bisect import bisect_left,bisect
from heapq import heappop,heappush,heapify
from math import ceil, floor, sqrt
from copy import deepcopy

def main():
    n = int(input())
    
    if n == 0:
        print(0)
        return

    ans = ""
    while n:
        if n%2:
            n -= 1
            ans += "1"
        else:
            ans += "0"
        n //= (-2)

    print(ans[::-1])


def __starting_point():
    main()
__starting_point()

import math
from math import gcd,pi,sqrt
INF = float("inf")

import sys
sys.setrecursionlimit(10**6)
import itertools
from collections import Counter,deque
def i_input(): return int(input())
def i_map(): return list(map(int, input().split()))
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_str(N): return [s_list() for _ in range(N)]
def s_row_list(N): return [list(s_input()) for _ in range(N)]

def main():
    n = i_input()
    l = []
    cnt = 0
    while True:
        if cnt%2 == 0:
            l.append(n%2)
            n = -(n//2)
            cnt += 1
        else:
            l.append(n%2)
            n = -(n//2)
            cnt += 1
        if n == 0:
            break
        # break
    l.reverse()
    print(("".join(map(str,l))))


def __starting_point():
    main()

__starting_point()

def main():
    n = int(input())
    ans = [] if n != 0 else [0, ]
    while n:
        ans.append(-(n % -2))
        n = -(n // 2)
    print((''.join(list(map(str, ans[::-1])))))

def __starting_point():
    main()

__starting_point()

n = int(input())

amari = []

while True:
    if n >1 or n<0:
        amari.append(-(n%(-2)))
        n = (n-(-(n%(-2))))//(-2)
    else:
        amari.append(n)
        break

gyaku = amari[::-1]
print(*gyaku,sep="")

import sys,math,collections,itertools
input = sys.stdin.readline

N=int(input())
s = []
if N ==0:
    print((0))
    return
    
while N:
    r = N%(-2)
    if r<0:
        r+=2
    N = (N-r)//(-2)
    s.append(str(r))

print((''.join(s)[::-1]))


N = int(input())
s = ""
i = 0

while N != 0:
    if N % 2 == 0:
        s += "0"
        N //= 2
    else:
        s += "1"
        if i % 2 == 0:
            N = (N - 1)//2
        else:
            N = (N + 1)//2
    i += 1

if s == "":
    print("0")
else:
    print(s[::-1])

import sys
stdin = sys.stdin
sys.setrecursionlimit(10**6)
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

n = ni()
a = 2
ans = ''

if n==0:
    print(0)
    return

while n != 0:
    if n%a == 0:
        ans = '0' + ans
    else:
        ans = '1' + ans
        n-=(a//2)
    a*=(-2)

print(ans)

n=int(input())
if n==0:
  print((0))
  return
ans=[]
while n!=0:
  n-=1
  ans.append(n%-2)
  n//=(-2)
#print(ans)
tmp=[1*(i==0) for i in ans][::-1]
print(("".join(map(str,tmp))))


def IntBaseConvert(N,K):
    if (type(N) is int) and (type(K) is int):
        if K>=2 and N>=0:
            if N==0:
                return [0]
            else:
                ConvertNum = []
                while N>0:
                    ConvertNum.append(N%K)
                    N = N//K
                return ConvertNum[::-1]
        elif K<=-2:
            if N==0:
                return [0]
            else:
                ConvertNum = []
                while abs(N)>0:
                    ConvertNum.append(N%abs(K))
                    N = (N-N%abs(K))//K
                return ConvertNum[::-1]
        else:
            return []
    else:
        return []
      
ConvertNum = IntBaseConvert(int(input()),-2)
print(''.join(str(T) for T in ConvertNum))

import sys
 
N = int(sys.stdin.readline())
if N == 0:
    print(0)
    return
binN = ""
pN = abs(N)
while N != 0:
    if abs(N % -2) == 1:
        binN += "1"
    else:
        binN += "0"
    N += N%(-2)
    N //= -2
print(binN[::-1])

n = int(input())
c = 0
while 1:
    c += 1
    if n == 0:
      break
    if n > 0:
        if c%2 == 1: 
            if (4**(c//2+1)-1)//3 >= n:
                break
    elif n < 0:
        if c%2 == 0:
            if abs(2*(4**(c//2)-1))//3 >= abs(n):
                break
if n == 0:
    ans = ["0"]
else:
    k = 0
    ans = []
    while k < c:
        ans.append(str(n%2))
        n = (-1)* (n//2)
        k += 1
print("".join(ans[::-1]))

def BaseM2Num(N):
    if N==0:
        return [0]
    else:
        List = []
        while abs(N)>0:
            if N%2==0:
                N //= (-2)
                List.append(0)
            else:
                N = (N-1)//(-2)
                List.append(1)
        return List[::-1]
      
List = BaseM2Num(int(input()))
print(''.join(str(T) for T in List))

# C - Base -2 Number

N = int(input())

ans = ''
if N == 0:
    ans = '0'
while N != 0:
    if N % 2 == 1:
        ans = '1' + ans
        N -= 1
    else:
        ans = '0' + ans
    N //= -2
print(ans)


N = int(input())

res = []
sign = 1
while N:
    if N%2 == 0:
        res.append(0)
    else:
        N -= sign
        res.append(1)
    N //= 2
    sign *= -1
if not res:
    res = [0]
print(*reversed(res),sep='')

import sys
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 8)
from itertools import accumulate
from itertools import permutations
from itertools import combinations
from collections import defaultdict
from collections import Counter
import fractions
import math
from collections import deque
from bisect import bisect_left
from bisect import bisect_right
from bisect import insort_left
import itertools
from heapq import heapify
from heapq import heappop
from heapq import heappush
import heapq
from copy import deepcopy
from decimal import Decimal
alf = list("abcdefghijklmnopqrstuvwxyz")
ALF = list("ABCDEFGHIJKLMNOPQRSTUVWXYZ")
#import numpy as np
INF = float("inf")
#d = defaultdict(int)
#d = defaultdict(list)
s = ""
N = int(input())
if N == 0:
    print(0)
else:
    while N != 0:
        x = N % (-2)
        if x == 0:
            s = "0"+s
            N = N // (-2)
        else:
            N = N//(-2)+1
            s = "1" + s

    print(s)

n = int(input())
ans = ''
while n!=0:
    r = n%2
    n = (n-r) // (-2)
    ans += str(r)
print(ans[::-1] if ans else 0)

N = int(input())
def po(n,k):
    if k <= 0:
        return 0 <= n <= 1
    if k % 2 == 0 and -2*(2**k-1)//3 <= n <= (2**(k+2)-1)//3:
        return True
    elif k % 2 == 1 and -2*(2**(k+1)-1)//3 <= n <= (2**(k+1)-1)//3:
        return True
    return False

def f(n):
    k = 0
    while True:
        if po(n,k):
            break
        k += 1
    ls = []
    while k >= 0:
        if po(n-(-2)**k, k-1):
            n -= (-2)**k
            ls.append("1")
        else:
            ls.append("0")
        k -= 1
    return "".join(ls)
print(f(N))

import sys
import math
from collections import defaultdict, deque, Counter
from copy import deepcopy
from bisect import bisect, bisect_right, bisect_left
from heapq import heapify, heappop, heappush
    
input = sys.stdin.readline
def RD(): return input().rstrip()
def F(): return float(input().rstrip())
def I(): return int(input().rstrip())
def MI(): return map(int, input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int, input().split()))
def TI(): return tuple(map(int, input().split()))
def LF(): return list(map(float,input().split()))
def Init(H, W, num): return [[num for i in range(W)] for j in range(H)]
    
    
def main():
    N = I()
    if N == 0:
        print(0)
        return
    if N < 0:
        N = -N
        D = defaultdict(int)
        index = 0
        while N >= 1:
            #bitフラグがたっていたら
            if N & 1 == 1:
                #2の倍数の場合D[index]とD[index+1]に1を足す
                if index % 2 == 0:
                    D[index] += 1
                    D[index+1] += 1
                else:
                    D[index] += 1
            else:
                D[index] = D[index]
            N = N>>1
            index += 1
    else:
        D = defaultdict(int)
        if N & 1 == 1:
            D[0] = 1
        else:
            D[0] = 0
        index = 1
        N = N >> 1

        while N >= 1:
            #bitフラグがたっていたら
            if N & 1 == 1:
                #2の倍数の場合D[index]とD[index+1]に1を足す
                if index % 2 == 1:
                    D[index] += 1
                    D[index+1] += 1
                else:
                    D[index] += 1
            else:
                D[index] = D[index]
            N = N>>1
            index += 1
            
            
    index = 0
    while True:
        if not index in D.keys():
            break
        if D[index] <= 1:
            pass
        else:
            temp = D[index]
            D[index] = temp % 2
            D[index+1] += (temp // 2)
            D[index+2] += (temp // 2)
            if D[index+1] >= D[index+2] * 2:
                temp = D[index+2]
                D[index+2] -= temp
                D[index+1] -= temp * 2
        index += 1
    res = True

    for i in reversed(D.values()):
        if res and i == 1:
            res = False
        if not res:
            print(i, end="")
    print()

def __starting_point():
    main()
__starting_point()

n = int( input() )

if n == 0:
    print('0')
else:
    sum = 0
    i = 0
    S = []
    while n != 0:

        x = n % (2 ** (i+1))
        if x != 0:
            S.append('1')

            n -= (-2) ** i

        else:
            S.append('0')
        i += 1
    
    S = S[::-1]
    strS = ''.join(S)
    print(strS)


#coding:utf-8

import sys
import bisect

SUM_P = [2**x for x in range(0, 31, 2)]
SUM_M = [2**x for x in range(1, 31, 2)]
for i in range(len(SUM_P)-1):
    SUM_P[i+1] += SUM_P[i]
for i in range(len(SUM_M)-1):
    SUM_M[i+1] += SUM_M[i]


N = int(input())

ret = 0
while N != 0:
    if N > 0:
        idx = bisect.bisect_left(SUM_P, N)
        idx = idx * 2
        N -= 2 ** idx
        ret += 2**idx
    else:
        idx = bisect.bisect_left(SUM_M, abs(N))
        idx = (idx * 2) + 1
        N += 2 ** idx
        ret += 2**idx

print((format(ret, "b")))


N = int(input())
ans = [] if N != 0 else [0]
while N:
    ans.append(-(N % -2))
    N = -(N // 2)
print(("".join(map(str, ans[::-1]))))


N = int(input())

s = ""

while N != 0:
    # Pythonでは負の数を割っても余りが正になる
    # -2で割ったときの"理想的な"余り(0or1になってくれる)は2で割った余りと同じ
    # -2で割ったときの余りは0or-1となってしまう、-1となったら1に置き換えるとしても良い
    r = int(N % 2)
    # ここは素直に-2
    N = (N - r) / (-2)
    s += str(int(r))

# N=0の時は空文字列が返ってきてしまう
if s == "":
    print((0))
    return
else:
    # reverse
    print((s[::-1]))


import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N = int(readline())

    ans = []
    while abs(N) > 0:
        ans.append(N % 2)
        N //= 2
        N *= -1

    if ans:
        ans = ''.join(map(str, reversed(ans)))
    else:
        ans = 0

    print(ans)
    return


def __starting_point():
    main()

__starting_point()

N = int(input())

basis = [(-2) ** d for d in range(64)]
cs = [1, -2]
for i in range(2, len(basis)):
    cs.append(cs[i - 2] + basis[i])

S = ['0'] * len(basis)

n = N
max_i = 0
while n != 0:
    if n > 0:
        for i in range(0, len(basis), 2):
            if cs[i] >= n:
                S[i] = '1'
                n -= basis[i]
                max_i = max(max_i, i)
                break
    else:
        for i in range(1, len(basis), 2):
            if cs[i] <= n:
                S[i] = '1'
                n -= basis[i]
                max_i = max(max_i, i)
                break

print((''.join(S[:max_i + 1])[::-1]))


import bisect, collections, copy, heapq, itertools, math, string, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def resolve():
    N = I()

    if N == 0:
        print((0))
    else:
        ans = []
        while abs(N) > 0:
            r = N % 2
            ans.append(r)
            if r == 1:
                N -= 1
            N //= -2

        print((''.join([str(i) for i in reversed(ans)])))

def __starting_point():
    resolve()

__starting_point()

N = -int(input())
a = ""

while N:
  a+=str(N%2)
  N//=-2

if a=="":
  print(0)
else:
  print(a[::-1])

#!/usr/bin/env python

n = int(input())

if n == 0:
    print((0))
    return

ans = ''
while abs(n) > 0:
    r = n%2 
    ans += str(r) 
    n //= 2
    n = -n

if abs(n)%2 == 1:
    print(ans)
else:
    print((ans[::-1]))


n = int(input())

dp =[0]*40

if n ==0:
    print(0)

elif n >0:
    x = bin(n)
    bx = x[2:]
    lx = len(bx)
    for i in range(lx-1,-1,-1):
        dp[i] = int(bx[lx-1-i])
    for i in range(40):
        if i % 2 ==1 and dp[i]==1:
            dp[i+1] +=1
    while max(dp) >1:
        for i in range(40):
            if dp[i] >=2:
                dp[i] -=2
                if dp[i+1] >0:
                    dp[i+1] -=1
                else:
                    dp[i+1] +=1
                    dp[i+2] +=1
    dpr = list(reversed(dp))
    dprs = list(map(lambda x :str(x),dpr))
    dprj = "".join(dprs)
    print(int(dprj))    

else:
    x = bin(-n)
    bx = x[2:]
    lx = len(bx)
    for i in range(lx-1,-1,-1):
        dp[i] = int(bx[lx-1-i])
    for i in range(40):
        if i % 2 ==0 and dp[i]==1:
            dp[i+1] +=1
    while max(dp) >1:
        for i in range(40):
            if dp[i] >=2:
                dp[i] -=2
                if dp[i+1] >0:
                    dp[i+1] -=1
                else:
                    dp[i+1] +=1
                    dp[i+2] +=1
    dpr = list(reversed(dp))
    dprs = list(map(lambda x :str(x),dpr))
    dprj = "".join(dprs)
    print(int(dprj))    

n=int(input())
ans=[]
if n==0:
    print(0)
    return
while True:
    if n==0:
        break
    if n>=0:
        ans.append(n%2)
        n=(-1)*(n//2)
    else:
        ans.append((n*-1)%2)
        if (n*-1)%2==1:
            n=(n*-1)//2+1
        else:
            n=(n*-1)//2
    

for i in range(len(ans)):
    ans[i]=str(ans[i])
print("".join(list(ans[::-1])))

n=int(input());result=[]
while n!=0:
  r=n%2
  n=(n-r)//-2
  result.append(r)
print(''.join(map(str,result[::-1])) if result else 0)

N = int(input())
a = ""
if N ==0:
  a =0
while N !=0:
  if N%2 != 0:
    a = "1" + a
  else:
    a = "0" + a
  N = - (N//2)
print(a)

n=int(input());result=[]
while n!=0:
  r=n%2
  n=(n-r)//-2
  result.append(r)
print(''.join(map(str,(result[::-1]))) if result else 0)

N = int(input())
S = list()
if N==0:
  print((0))
  return
elif N>0:
  while N>0:
    S.append(N%2)
    N//=2
  S.append(0)
  S.append(0)
  for i in range(len(S)-1):
    if i%2==1 and S[i]==1:
      S[i+1] += 1
    if S[i]==2:
      S[i]=0
      S[i+1]+=1
else:
  N *= -1
  while N>0:
    S.append(N%2)
    N//=2
  S.append(0)
  S.append(0)
  for i in range(len(S)-1):
    if i%2==0 and S[i]==1:
      S[i+1] += 1
    if S[i]==2:
      S[i]=0
      S[i+1]+=1
  
S.reverse()
while S[0]==0:
  S = S[1:]
ans = ""
for s in S:
  ans += str(s)
print(ans)


n = int(input())
if n == 0:
  print(0)
  return
s = ""
while n != 0:
  m = abs(n % -2)
  s = str(m) + s
  n = (n - m) // -2
print(s)

N = int(input())


def max_pos_number(n):
    val = 0
    for i in range(n):
        if i % 2 == 0:
            val += 2**i
    return val


def min_pos_number(n):
    val = 0
    for i in range(n):
        if i % 2 == 1:
            val -= 2**i

    return val


n = 1
while True:
    if min_pos_number(n) <= N <= max_pos_number(n):
        break
    n += 1

result = []
for i in range(n-1, -1, -1):
    if i % 2 == 0:
        if N > max_pos_number(i):
            result.append(1)
            N -= (-2) ** i
        else:
            result.append(0)
    else:
        if N < min_pos_number(i):
            result.append(1)
            N -= (-2) ** i
        else:
            result.append(0)
print((''.join([str(x) for x in result])))


N = int(input())
ans = ""

if N==0:
  print(0)
else:
  while N!=0:
    ans+=str(N%2)
    N=-(N//2)
  print(ans[::-1])

x=[0]*32
x[0]=1
x[1]=-2
for i in range(2,32):
  x[i]=x[i-2]+(-2)**i
n=int(input())
if n==0:
  print(0)
  return
ans=''
for i in range(2,33)[::-1]:
  if i%2:
    l=x[i-2]
    r=x[i-1]
  else:
    l=x[i-1]
    r=x[i-2]
  t=n-(-2)**i
  if l<=t and t<=r:
    n=t
    ans=ans+'1'
  else:
    ans=ans+'0'
ls=['10','11','00','01']
ans=ans+ls[n+2]
for i in range(len(ans)):
  if ans[i]=='1':
    re=i
    break
print(ans[re:])

n = int(input())
if n == 0:
  print(0)
  return
a = [1]
p = [1]
m = [0]
hi = [1]
lo = [1]
i = 0
while(True):
  if n >= lo[i] and n<= hi[i]:
    break
  i += 1
  a.append(a[i-1]*-2)
  if i%2==0:
    p.append(p[i-1]+a[i])
    m.append(m[i-1])
  else:
    p.append(p[i-1])
    m.append(m[i-1]+a[i])
  hi.append(a[i]+p[i-1])
  lo.append(a[i]+m[i-1])
ans = []
for j in range(i+1)[::-1]:
  if n >= lo[j] and n<= hi[j]:
    ans.append(1)
    n-=a[j]
  else:
    ans.append(0)
print(*ans,sep="")


N = int(input())

def base(x, n):
  ret = []
  while x != 0:
    ret.append( x % abs(n))
    if n < 0:
      x = - ( (-x)//n )
    else:
      x //= n
  return ret

if N == 0:
  print(0)
else:
  print("".join(map(str, reversed(base(N, -2)))))

n =  int(input())
x = ''
while n != 0:
    x = str(n%2) + x
    n = -(n//2)
print((0 if x == '' else x))


import sys

N = int(sys.stdin.readline())
if N == 0:
    print(0)
    return
binN = ""
pN = abs(N)
while N != 0:
    if abs(N % -2) == 1:
        binN += "1"
    else:
        binN += "0"
    N += N%(-2)
    N //= -2
print(binN[::-1])

n = int(input())
if n==0:
  print(0)
  return
if n==1:
  print(1)
  return
l = []
while n!=1:
  if n%2==0:
    n //= -2
    l.append(0)
  else:
    n = (n-1)//(-2)
    l.append(1)
l.append(1)
l = l[::-1]
print(*l,sep="")