local DBG = false
local function dbgpr(...)
    if DBG then
        io.write("[dbg]")
        print(...)
    end
end

local function baseneg2_tostr(t)
    if #t == 0 then
        return "0"
    else
        local r = {}
        for i=#t,1,-1 do
            table.insert(r, t[i])
        end
        return table.concat(r, "")
    end
end

local function baseneg2_to_dec(t)
    if #t == 0 then
        return 0
    else
        local n = 0
        for i=0,#t-1 do
            n = n + t[i+1]*(-2)^i
        end
        return math.floor(n)
    end
end

local function dec_to_baseneg2(n)
    dbgpr("dec_to_baseneg2", n)
    local t = {}
    local i = 1
    while n ~= 0 do
        local b = math.floor((-2)^i)
        local bb = math.floor((-2)^(i-1))
        dbgpr("ibnbb", i, b, n, bb)
        local q, r = math.abs(n // b) - 1, nil
        while true do
            dbgpr("rem", n, q, b*q, b*-q, bb)
            if n == b * q then
                q = q
                r = 0
                break
            elseif n == b * q + bb then
                q = q
                r = 1
                break
            elseif n == b * -q then
                q = -q
                r = 0
                break
            elseif n == b * -q + bb then
                q = -q
                r = 1
                break
            end
            q = q + 1
        end
        local rr = r * bb
        dbgpr("r rr", r, rr)
        n = n - rr
        dbgpr("newn", n)
        table.insert(t, r)
        i = i + 1
    end
    return t
end

local function test(n)
    local t = dec_to_baseneg2(n)
    --print("res", n, baseneg2_tostr(t))
    assert(n == baseneg2_to_dec(t))
end


test(0)
test(1)
test(-2)
test(-1)
test(-9)
test(123456789)

print(baseneg2_tostr(dec_to_baseneg2(io.read("n"))))
