import functools
i = 0
O = 0
E = 0

@functools.lru_cache
def pow3(n):
    return 3**n

def dc(x0,dep,is_r):
    global x,i,O,E
    n = 2**dep
    if dep:
        x1 = x0
        if x1>>n: x1 &= (1<<n)-1
        x1,y1 = dc(x1,dep-1,0)
        x1,y2 = dc(x1,dep-1,1)
        y0 = y1*pow3(n//2)+(y2<<(n//2))
    else:
        y0 = x0%2
        i += 1
        O += y0
        E += 1-y0
        b = E*2-O
        assert b>=0
        if i==i&-i:
            print(i,b,b-i//2)
    if is_r: x0 = None
    else: x0 = (x0*pow3(n)-y0)>>n
    return x0,y0

dc(8,64,1)