from itertools import takewhile

def log2(n):
    m = 0
    while True:
        n >>= 1
        if not n:
            break
        m += 1
    return m

def data_bits_for_power(power):
    mask = 2 ** power
    i = 3
    while True:
        if i & mask and i != mask:
            yield i
        i += 1

def max_bit(power):
    return (2 ** power) - 1

def max_data_bit(power):
    return (2 ** power) - power - 1

def filter_max_bit(power, it):
    return list(takewhile(lambda i: i <= max_bit(power), it))

def input_data_bits(max_power):
    def go():
        for power in range(max_power):
            yield set(map(output_index.data_bit,
                           filter_max_bit(max_power, data_bits_for_power(power))))
    return list(go())

def generator_matrix(max_power):
    idb = input_data_bits(max_power)
    def go():
        for d in range(max_data_bit(max_power)):
            yield [
                int(d in idb[p])
                for p in range(max_power)
            ]
    return list(go())

def identity_matrix(max_power):
    max_bit = max_data_bit(max_power)
    def go():
        for d in range(max_bit):
            l = [0] * max_bit
            l[d] = 1
            yield l
    return list(go())

def rowwise_concatenate(ma, mb):
    assert len(ma) == len(mb)
    def go():
        for row_ix in range(len(ma)):
            yield [*ma[row_ix], *mb[row_ix]]
    return list(go())

class input_index:
    @staticmethod
    def data_bit(n):
        assert n > 2
        return n - log2(n) - 2

    @staticmethod
    def parity_bit(n):
        assert 2 ** log2(n) == n
        return log2(n)

# list(map(input_index.data_bit, filter_max_bit(3, data_bits_for_power(0))))