def bin_to_int(bin_num):
    return int(bin_num, 2)


def parse_literal(bin_num):
    res = ""
    i = 0
    while True:
        res += bin_num[i+1:i+5]
        i += 5
        if bin_num[i-5] == '0':
            break
    return bin_to_int(res), i


def parse_op(bin_num):
    if bin_num[0] == '0':
        length = bin_to_int(bin_num[1:16])
        return parse_packets(bin_num[16:16+length]), length+16
    else:
        amount = bin_to_int(bin_num[1:12])
        pkgs = []
        i = 0
        for _ in range(amount):
            pkg, length = parse_packet(bin_num[12+i:])
            pkgs.append(pkg)
            i += length
        return pkgs, 12+i


def parse_packet(bin_num):
    ver = bin_to_int(bin_num[:3])
    op = bin_to_int(bin_num[3:6])
    if op == 4:
        value, length = parse_literal(bin_num[6:])
    else:
        value, length = parse_op(bin_num[6:])
    return (ver, op, value), length + 6


def parse_packets(bin_num):
    pkgs = []
    i = 0
    while '1' in bin_num[i:]:
        pkg, length = parse_packet(bin_num[i:])
        pkgs.append(pkg)
        i += length
    return pkgs