import sys

import psyco; psyco.full()

def remove_header(s):
    if s.startswith("00101101"):
        return s[8:]

    raise Exception("DSDDDSDDS")

def check_preamble(s):
    row = 0
    col = 1

    p = ""
    while len(p) < 56:
        for i in xrange(col, 8):
            p += s[row*8+i]

        row += 1
        if row % 2 == 0:
            col += 1

    if p == "01010110011011101101001001110001011110010100011000010000":
        #print "preamble OK"
        pass

def deconv(s):
    out = ""
    numbits = 0
    byte = 0

    pos = 0
    prevs = [0, 0, 0, 0]
    g = [0, 0, 0, 0]

    while pos < len(s) - 4:
        z0 = (0 + prevs[-2] + prevs[-4]) % 2
        z1 = (0 + prevs[-2] + prevs[-3] + prevs[-4]) % 2
        z2 = (0 + prevs[-1] + prevs[-3] + prevs[-4]) % 2
        z3 = (0 + prevs[-1] + prevs[-2] + prevs[-3] + prevs[-4]) % 2

        o0 = (1 + prevs[-2] + prevs[-4]) % 2
        o1 = (1 + prevs[-2] + prevs[-3] + prevs[-4]) % 2
        o2 = (1 + prevs[-1] + prevs[-3] + prevs[-4]) % 2
        o3 = (1 + prevs[-1] + prevs[-2] + prevs[-3] + prevs[-4]) % 2

        zs = "%d%d%d%d" % (z0, z1, z2, z3)
        os = "%d%d%d%d" % (o0, o1, o2, o3)

        if s[pos:pos+4] == zs:
            #print "Found bit 0"
            prevs.append(0)
            g = [z0, z1, z2, z3]
        elif s[pos:pos+4] == os:
            #print "Found bit 1"
            prevs.append(1)
            g = [o0, o1, o2, o3]
        else:
            print "failed to deconv"
            print "actual", s[pos:pos+4]
            print "expected 0", zs
            print "expected 1", os
            return pos

        byte |= (prevs[-1] << numbits)
        numbits += 1

        if numbits == 8:
            out += chr(byte)
            byte = 0
            numbits = 0
            print repr(out)
        pos += 4

    return pos

def deinterleave(s):
    start = 0
    pos = 0
    col = 0
    out = ""
    while pos < len(s):
        c = s[pos]
        if c == "X":
            #print "X at ", len(out)
            out += c
        elif c == "Z":
            out += c
        else:
            if col in (0, 2, 3, 6, 7):
                if c == "0":
                    out += "1"
                else:
                    out += "0"
            else:
                if c == "0":
                    out += "0"
                else:
                    out += "1"

        pos += 17
        col += 1
        if col == 8:
            start += 8
            pos = start
            col = 0

    # print out
    # print len(out)

    return out

def main():
    best = 0
    data = "310231103210010213123213202021122323003013330012031312330323"
    data += "X" * 16
    data += "133210200332321211220313013012011210122323103203000203322301300301100220231030020102022223133003010302220313100321030222211302030103322233332103232322222333233323122310230023012300230023"

    # data = "310231103210010213123213202001122323303013330212131333332203"
    # data += "X" * 16
    # data += "0002013100203211110000013323100002031130203332300121032323003011011202222311300301020222231330030103022203131003210302222113020301033222333321032323222223332333231223102300230123032303"

    # for i in xrange(100, len(data)):
        # for c in "0123":
            # res = loop(data[:i] + c + data[i+1:])
            # if res > best:
                # print data[:i] + c + data[i+1:]
                # print i, c, res
                # best = res

    loop(data)
def loop(data):


    s = ""
    for c in data:
        if c == "0":
            s += "11"
        elif c == "1":
            s += "10"
        elif c == "2":
            s += "01"
        elif c == "3":
            s += "00"
        elif c == "X":
            s += "XX"
        elif c == "Z":
            s += "ZZ"


    s = remove_header(s)

    check_preamble(s)

    s = deinterleave(s)

    if s[352:384] == "01010110011011101101001001110001":
        #print "resync OK"
        s = s[:352] + s[384:]
    else:
        print "resync failed!"
        return 0

    ss = ""
    for c in s:
        if c in "Z01":
            ss += c

    s = ss

    #print s

    return deconv(s)

main()