#!/usr/bin/env python3
from functools import reduce

def generate_tests():
    def test0():
        a = [[0, 1, 0, 1],
             [0, 0, 0, 0],
             [0, 0, 0, 0],
             [1, 0, 0, 1]]
        return (a, 2, 2)

    def test1():
        a = [[1, 1, 0, 1],
             [1, 0, 0, 0],
             [0, 0, 0, 1],
             [1, 0, 1, 1]]
        return (a, 2, 2)

    def test2():
        a = [[1, 1, 1, 1],
             [0, 0, 0, 0],
             [0, 0, 0, 1],
             [1, 0, 1, 1]]
        return (a, 2, 2)

    def test3():
        a = [[1, 1, 0, 1],
             [0, 0, 0, 0],
             [1, 0, 0, 1],
             [1, 0, 1, 1]]
        return (a, 2, 2)

    def test4():
        a = [[0, 1, 0, 1],
             [0, 0, 0, 0],
             [0, 0, 0, 0],
             [1, 0, 0, 1]]
        return (a, 3, 3)

    def test5():
        a = [[1, 1, 0, 0],
             [1, 1, 0, 0],
             [0, 0, 1, 1],
             [0, 0, 1, 1]]
        return (a, 2, 2)

    def test6():
        a = [[0, 1, 1, 0],
             [0, 0, 0, 0],
             [0, 0, 0, 0],
             [1, 0, 1, 0]]
        return (a, 2, 2)
    test_func_prefix = 'test'
    test_namespace = locals()

    return [(x, test_namespace[x]()) for x in \
            filter(lambda x: x.startswith(test_func_prefix) \
            and callable(test_namespace[x]), test_namespace)]

def output(test_name, succeed, log):
    print("%s %s %s" % (test_name, "succeeds" if succeed else "fails", log))

def cut(sum_matrix, value_per_portion, portion_num, option):
    def total_value(last_pos, cur_pos):
        if last_pos == -1:
            return sum_matrix[cur_pos][-1] if option == 'r' else sum_matrix[-1][cur_pos]

        return sum_matrix[cur_pos][-1] - sum_matrix[last_pos][-1] if option == 'r' else \
            sum_matrix[-1][cur_pos] - sum_matrix[-1][last_pos]

    cur_pos = 0
    last_pos = -1
    max_pos = len(sum_matrix) if option == 'r' else len(sum_matrix[0])

    cur_value = 0

    strategy = []

    while cur_pos < max_pos:
        while (cur_pos < max_pos) and \
            (total_value(last_pos, cur_pos) < value_per_portion):
            cur_pos += 1

        if total_value(last_pos, cur_pos) != value_per_portion:
            return None

        move = [cur_pos]
        while (cur_pos + 1 < max_pos) and (total_value(cur_pos, cur_pos + 1) == 0):
            cur_pos += 1
            move.append(cur_pos)

        strategy.append(move)
        last_pos = cur_pos
        cur_pos += 1

    return strategy

def validate(sum_matrix, r_stg, c_stg, value_per_portion):

    def compute(r_cut_idx, c_cut_idx):
        v = sum_matrix[r_stg[r_cut_idx][0]][c_stg[c_cut_idx][0]]
        if c_cut_idx != 0:
            v -= sum_matrix[r_stg[r_cut_idx][0]][c_stg[c_cut_idx-1][0]]

        if r_cut_idx != 0:
            v -= sum_matrix[r_stg[r_cut_idx-1][0]][c_stg[c_cut_idx][0]]

        if (c_cut_idx != 0) and (r_cut_idx != 0):
            v += sum_matrix[r_stg[r_cut_idx-1][0]][c_stg[c_cut_idx-1][0]]

        return v

    r_cut_cnt, c_cut_cnt = len(r_stg), len(c_stg)
    values = [compute(i, j) for j in range(c_cut_cnt) for i in range(r_cut_cnt)]
    return all(map(lambda v: v == value_per_portion, values))

def generate_sum_matrix(m):
    r_num, c_num = len(m), len(m[0])
    sum_matrix = [[0 for _ in range(c_num)] for _ in range(r_num)]

    for r in range(r_num):
        r_sum = 0
        for c in range(c_num):
            if r > 0: sum_matrix[r][c] = sum_matrix[r-1][c]
            r_sum += m[r][c]
            sum_matrix[r][c] += r_sum
    return sum_matrix

# assumption: input is always valid
def process(m, r_cut, c_cut):
    r_num, c_num = len(m), len(m[0])
    # empty input
    if r_num == 0: return None

    total_num = reduce(lambda x, y: x + y, [reduce(lambda x, y: x + y, row) for row in m])
    if total_num % (c_cut*r_cut) != 0:
        return False, "Invalid number of 1s giving the cutting requirement"

    sum_matrix = generate_sum_matrix(m)

    r_stg = cut(sum_matrix, total_num / r_cut, r_cut, 'r')
    if r_stg is None:
        return False, "No valid row cutting strategy"

    c_stg = cut(sum_matrix, total_num / c_cut, r_cut, 'c')
    if c_stg is None:
        return False, "No valid column cutting strategy"

    if not validate(sum_matrix, r_stg, c_stg,
            total_num / (c_cut*r_cut)):
        return False, "Possible cutting strategies don't work"

    return True, "row cuts %s, col cuts: %s" % (str(r_stg), str(c_stg))

if __name__ == "__main__":
    for test_name, inputs in generate_tests():
        output(test_name, *process(*inputs))