====== Example solutions ====== of selected older exam programming problems ====== Gallery Guards ====== [[https://cw.felk.cvut.cz/brute/data/ae/release/2021l_be5b33pge/pge2021/evaluation/input.php?task=gallery_py|problem description]]


#  ---------------------------------------------------------------------------------------------
#  solution 1
#  ---------------------------------------------------------------------------------------------

import sys

# read G, P
line = sys.stdin.readline()
terms = line.strip().split(', ')
G = int(terms[0])
P = int(terms[1])

# read guard names
line = sys.stdin.readline()
guards = line.strip().split(', ')
guard_dict = {
    guard: [[0] * 600, [0] * 600] for guard in guards
}

# read gallery names
line = sys.stdin.readline()
terms = line.strip().split(', ')

gallery_dict = {
    terms[0]: 0,
    terms[1]: 1
}

gallery_time_list = [[0] * 600, [0] * 600]
for _ in range(P):
    line = sys.stdin.readline()
    terms = line.strip().split(', ')

    # get guard name
    guard = terms[0]

    # get start and end times
    h, m = terms[1].split(':')
    start = int(h) * 60 + int(m) - 8 * 60
    start = max(start, 0)

    h, m = terms[2].split(':')
    end = int(h) * 60 + int(m) - 8 * 60
    end = min(end, 599)

    if start > end:
        continue

    # get gallery index
    gallery_index = gallery_dict[terms[3]]

    for i in range(start, end + 1):
        # update free time
        gallery_time_list[gallery_index][i] = 1

        # update conflict time
        guard_dict[guard][gallery_index][i] = 1

# calculate free time
free_time = [0, 0]
for i, gallery_time in enumerate(gallery_time_list):
    for j in gallery_time:
        if j == 0:
            free_time[i] += 1

# calculate conflict time
conflict_dict = {}
for guard in guard_dict:
    conflict_time = 0
    for i in range(600):
        if guard_dict[guard][0][i] == guard_dict[guard][1][i] == 1:
            conflict_time += 1

    conflict_dict[guard] = conflict_time

conflict_time_list = sorted(conflict_dict.items(), key=lambda kv: (kv[1], kv[0]))

# output free time
sys.stdout.write(f'{free_time[0]//60:0>2}:{free_time[0]%60:0>2}{free_time[1]//60:0>2}:{free_time[1]%60:0>2}')
sys.stdout.write('\n')

# output conflict time
for item in conflict_time_list:
    sys.stdout.write(f'{item[1] // 60:0>2}:{item[1] % 60:0>2} ')
    sys.stdout.write(item[0] + '\n')


#  ---------------------------------------------------------------------------------------------
#  solution 2
#  ---------------------------------------------------------------------------------------------
def Gallery_Guards():
    line1 = input()
    list1 = line1.split(', ')
    G = int(list1[0])
    P = int(list1[1])
    line2 = input()
    list2 = line2.split(', ')
    line3 = input()
    list3 = line3.split(', ')
    R1 = list3[0]
    R2 = list3[1]
    libm = {}
    for i in list2:
        libm[i] = 0
    lib1 = {}
    lib2 = {}
    for i in range(8,18):
        for j in range(60):
            lib1[60*i+j] = []
            lib2[60*i+j] = []
    for i in range(P):
        line4 = input()
        list4 = line4.split(', ')
        m = str(list4[0])
        R = str(list4[3])
        s = (int(list4[1].split(':')[0]))*60+int(list4[1].split(':')[1])
        e = (int(list4[2].split(':')[0]))*60+int(list4[2].split(':')[1])
        if R == R1:
            for j in range(s,e+1):
                if m not in lib1[j]:
                    c = lib1[j]
                    c.append(m)
                    lib1[j] = c
                    if m in lib2[j]:
                        libm[m] = libm[m] + 1
        else:
            for j in range(s,e+1):
                if m not in lib2[j]:
                    c = lib2[j]
                    c.append(m)
                    lib2[j] = c
                    if m in lib1[j]:
                        libm[m] = libm[m] + 1
    f1 = 0
    f2 = 0
    for value in lib1.values():
        if value == []:
            f1 += 1
    for value in lib2.values():
        if value == []:
            f2 += 1
    strlist = str(f'{f1//60:02}')+':'+str(f'{f1%60:02}')+' '+str(f'{f2//60:02}')+':'+str(f'{f2%60:02}')
    mlist = []
    for key in libm:
        mlist.append((key,libm[key]))
    def firsort(elem):
        return elem[0]
    def secsort(elem):
        return elem[1]
    mlist.sort(key=firsort)
    mlist.sort(key=secsort)
    for i in mlist:
        strlist += '\n'+str(f'{i[1]//60:02}')+':'+str(f'{i[1]%60:02}')+' '+i[0]
    return(strlist)
print(Gallery_Guards())


#  ---------------------------------------------------------------------------------------------
#  solution 3
#  ---------------------------------------------------------------------------------------------

def toHM( n ):
    return ("00" +str(n//60))[-2:] + ":" + ("00" +str(n%60))[-2:]

def register( item ):
    global gallery1, gallery2, gallery1free, gallery2free
    item = item.split(", ")
    t1 = toMinutes(item[1])
    t2 = toMinutes(item[2])
    iperson = personI[item[0]]
    if item[3] == gallery1name:
        gallery1[iperson][t1: t2+1] = [1] * (t2+1-t1)
        gallery1free[t1: t2+1] = [0] * (t2+1-t1)
    else:
        gallery2[iperson][t1: t2+1] = [1] * (t2+1-t1)
        gallery2free[t1: t2+1] = [0] * (t2+1-t1)

def solve():
    confltime = []
    for person in personI:
        conflt = 0
        iperson = personI[person]
        for i in range(minmin, maxmin+1):
            if gallery1[iperson][i] * gallery2[iperson][i] > 0:
                conflt += 1
        confltime.append( toHM(conflt) +" " + person)
    confltime.sort()
    
    print(toHM(sum(gallery1free)), toHM(sum(gallery2free)))
    print( "\n". join(confltime) )

#    M A I N

NP, Nit  = map(int, input().split(", "))
names = input().split(", ")

gallery1name, gallery2name = input().split(", ")
gallery1 = [[0]*(maxmin+1) for k in range(NP)]
gallery2 = [[0]*(maxmin+1) for k in range(NP)]
gallery1free = [0] * minmin + ([1]*(maxmin+1-minmin))
gallery2free = [0] * minmin + ([1]*(maxmin+1-minmin))

for i in range(NP):
    personI[names[i]] = i
for i in range(Nit):
    item = input()
    register(item)

#for k in gallery1: print(k)
#for k in gallery2: print(k)

solve ()

====== Rectangles area ====== [[https://cw.felk.cvut.cz/brute/data/ae/release/2021l_be5b33pge/pge2021/evaluation/input.php?task=rectanglesarea|problem description]]


#  ---------------------------------------------------------------------------------------------
#  solution 1
#  ---------------------------------------------------------------------------------------------
matrix = []
rows = 0
col = 0
num_rect = 0
total_area = 0
upper_left_container = []

def get_inputs():
    global matrix
    global rows
    global col

    rows, col = input().split()
    rows = int(rows)
    col = int(col)

    for row in range(rows):
        new_row = input().split()
        matrix.append(new_row)

    return matrix


def start_corner_finder():

    for y in range(rows-1):
        for x in range(col-1):
            if matrix[y][x] == "1":
                find_borders(y, x)


def find_borders(y1,x1):

    up = 1
    bottom = 1
    left = 0
    right = 1

    for y in range(y1, rows):
        if matrix[y][x1] == "1":
            left += 1
        else:
            break

    for x in range(x1+1, col):
        if matrix[y1][x] == "1":
            up += 1
        else:
            break

    if up > 2 and left > 2:
        for y in range(y1+1, rows):
            if matrix[y][x1+up-1] == "1":
                right += 1
            else:
                break
        for x in range(x1+1, col):
            if matrix[y1+left-1][x] == "1":
                bottom += 1
            else:
                break

    get_parameters(up,bottom,left, right)


def get_parameters(up, bottom, left, right):
    global num_rect
    global total_area

    if up > 2 and left > 2:
        if up == bottom and left == right:
            num_rect += 1
            area = (up-2)*(left-2)
            total_area += area


get_inputs()
start_corner_finder()
print(num_rect, total_area)

#  ---------------------------------------------------------------------------------------------
#  solution 2
#  ---------------------------------------------------------------------------------------------

import sys
 
try:
    basic = []
    while True:
        m = sys.stdin.readline().strip()
        if m == '':
            break
        m = list(m.split())
        basic.append(m)
    #print(basic)
except:
    pass
 
#basic = [['17', '4'], ['1', '1', '1', '1'], ['1', '0', '0', '1'], ['1', '1', '1', '1'], ['0', '0', '0', '0'], ['1', '1', '1', '1'], ['1', '0', '0', '1'], ['1', '1', '1', '1'], ['0', '0', '0', '0'], ['1', '1', '1', '1'], ['0', '0', '0', '0'], ['1', '1', '1', '1'], ['1', '0', '0', '1'], ['1', '1', '1', '1'], ['0', '0', '0', '0'], ['1', '1', '1', '0'], ['0', '0', '0', '0'], ['1', '1', '1', '1']]
 
for i in range(len(basic)):
    basic[i] = [int(num) for num in basic[i]]
 
R = basic[0][0]
C = basic[0][1]
basic.pop(0)
 
def find_sq(y, x):
    w = 0
    h = 0
    t = 0
    for a in range(x, C):
        if basic[y][a] == 1:
            w += 1
        else: break
    for b in range(y, R):
        if basic[b][x] == 1:
            h += 1
        else: break
    for c in range(w):
        if basic[y+h-1][x+c] != 1:
            t += 1
            break
    for d in range(h):
        if basic[y+d][x+w-1] == 0:
            t += 1
            break
    if t == 0:
        return w, h
    else: return 0, 0
 
num = 0
area = 0
for i in range(R-1):
    for j in range(C-1):
        wid = 0
        height = 0
        if basic[i][j] == 1:
            wid, height = find_sq(i, j)
            if wid >= 3 and height >= 3:
                num += 1
                area += (wid-2)*(height-2)
        else:
            basic[i][j] = 0
 
print(num, area)

#  ---------------------------------------------------------------------------------------------
#  solution 3
#  ---------------------------------------------------------------------------------------------
def get_rect(board, ci, ri, board_c, board_r):
    width, height = 1, 1
    for mc in range(ci + 1, board_c):
        if board[ri][mc] == "1":
            width += 1
        else:
            break

    if width < 2:
        return None

    for mr in range(ri + 1, board_r):
        if board[mr][ci] == "1":
            height += 1
        else:
            break

    if height < 2:
        return None

    # check bottom row
    for mc in range(ci + 1, ci+width):
        if board[ri+height-1][mc] != "1":
            return None

    # check right column
    for mr in range(ri + 1, ri+height):
        if board[mr][ci+width-1] != "1":
            return None

    return {
        "wh": (width, height),
        "cr": (ci, ri)
    }


def sum_area(rect_list):
    sa = 0
    for rect in rect_list:
        w, h = rect["wh"]
        sa += (w-2) * (h-2)
    return sa


def solve(board):
    rect_list = []

    board_r = len(board)
    board_c = len(board[0])

    for ri in range(board_r):
        for ci in range(board_c):
            if board[ri][ci] == "1":
                rect = get_rect(board, ci, ri, board_c, board_r)
                if rect:
                    rect_list.append(rect)

    areas = sum_area(rect_list)
    return len(rect_list), areas


def read_from_input():
    rc = input()
    r, c = rc.split()
    r, c = int(r), int(c)

    board = []
    for ri in range(r):
        line = input()
        row = line.split()
        board.append(row[:c])

    return board


def main():
    board = read_from_input()
    rect_num, rect_areas = solve(board)
    print(rect_num, rect_areas)


if __name__ == '__main__':
    main()
#  ---------------------------------------------------------------------------------------------
#  solution 4
#  ---------------------------------------------------------------------------------------------
import time
arr = []
M, N = list(map(int, input().split()))
t1 = time.time()
for i in range(M):
    line = list(map(int, input().split()))
    arr.append(line)
t2 = time.time()
range_rows = []
for n, lst in enumerate(arr):
    start = 0
    end = 0
    for i in range(N):
        if lst[i] == 1 and end == 0:
            start = i
            end = i+1
        elif lst[i] == 1 and end != 0 and i == N-1:
            range_rows.append((n, start, end))
        elif lst[i] == 1 and end!= 0:
            end += 1
        elif lst[i] == 0 and end == 0:
            end = 0
            start = 0
        elif lst[i] == 0 and end != 0:
            end -= 1
            range_rows.append((n, start, end))
            end = 0
            start = 0
range_rows = sorted(range_rows, key = lambda element: (element[1], element[2]))
poss_rect = []
for i in range(len(range_rows)- 1):
    if range_rows[i][1] == range_rows[i+1][1] and range_rows[i][2] == range_rows[i+1][2] and (range_rows[i][2]- range_rows[i][1]) > 1:
        poss_rect.append((range_rows[i], range_rows[i+1]))
    else:
        continue
rect = []
for points in poss_rect:
    first, second = points
    for i in range(first[0], second[0]):
        if arr[i][first[1]] != arr[i][second[1]] or  arr[i][first[2]] != arr[i][second[2]]:
            break
        elif arr[i][first[1]] == arr[i][second[1]] == 0 or arr[i][first[2]] == arr[i][second[2]]== 0:
            break
    else:
        rect.append(points)
area = 0
for values in rect:
    top, bottom = values
    area += (bottom[0]-top[0]-1)*(top[2]-top[1]-1)
t3 = time.time()
print(len(rect), area)
#print(t2-t1)
#print(t3-t2)

====== Cooperating Robot Pairs ====== [[https://cw.felk.cvut.cz/brute/data/ae/release/2020l_be5b33pge/pge2020/evaluation/input.php?task=cooppairs_py|problem description]]


#  ---------------------------------------------------------------------------------------------
#  solution 1
#  ---------------------------------------------------------------------------------------------
M, N = input().split()
M, N = [int(M), int(N)]
matrix = []
for row in range(M):
    matrix.append(list(map(int, input().split())))
degree_dict = {2:0, 3:0, 4:0, 5:0, 6:0, 7:0, 8:0}
checked = []

def isNeighbour(cell, matrix, M, N):
    count = 0
    neighbours = []
    for i in range(cell[1]+1, N): #right
        if matrix[cell[0]][i] == 2: break
        if matrix[cell[0]][i] == 1:
            neighbours.append((cell[0], i))
            count+=1
            break
    for i in range(cell[1]-1, -1, -1): #left
        if matrix[cell[0]][i] == 2: break
        if matrix[cell[0]][i] == 1:
            neighbours.append((cell[0], i))
            count+=1
            break
    for i in range(cell[0] - 1, -1, -1): #up
        if matrix[i][cell[1]] == 2: break
        if matrix[i][cell[1]] == 1:
            neighbours.append((i, cell[1]))
            count+=1
            break
    for i in range(cell[0] + 1, M): #down
        if matrix[i][cell[1]] == 2: break
        if matrix[i][cell[1]] == 1:
            neighbours.append((i, cell[1]))
            count+=1
            break
    listed= []
    listed.append(count)
    listed.append(neighbours)
    # print(listed)
    return listed

for row in range(M):
    for col in range(N):
        if matrix[row][col] == 1:
            data = isNeighbour([row, col], matrix, M, N)
            if data[0] == 0 : continue
            sumX = data[0] #first robot
            for cell in data[1]: #paired robots
                if((row, col), cell) in checked or (cell, (row, col)) in checked: continue
                checked.append(((row, col), cell))
                sumY = isNeighbour(cell, matrix, M, N)[0]
                degree_dict[sumX + sumY] += 1

for i in degree_dict:
    print(i, degree_dict[i])

    
#  ---------------------------------------------------------------------------------------------
#  solution 2
#  ---------------------------------------------------------------------------------------------
def check_pair_right(m: int, n: int):
    while True:
        if n + 1 <= N - 1:
            if p[m][n + 1] == 2:
                return (0, 0)
            elif p[m][n + 1] == 0:
                n += 1
                continue
            elif p[m][n + 1] == 1:
                return (m, n + 1)
        else:
            return (0, 0)

def check_pair_down(m: int, n: int):
    while True:
        if m + 1 <= M - 1:
            if p[m + 1][n] == 2:
                return (0, 0)
            elif p[m + 1][n] == 0:
                m += 1
                continue
            elif p[m + 1][n] == 1:
                return (m + 1, n)
        else:
            return (0, 0)


p = []
res = {i: 0 for i in range(2, 9)}
pairs = []

M, N = [int(i) for i in input().split()]
for m in range(M):
    p.append(list(int(i) for i in input().split()))

# Формируем список пар роботов
for m in range(M):
    for n in range(N):
        if p[m][n] == 1:
            r = check_pair_right(m, n)
            if r != (0, 0):
                pairs.append(((m, n), r))
            d = check_pair_down(m, n)
            if d != (0, 0):
                pairs.append(((m, n), d))

for pair in pairs:
    counter = 0
    for c in pairs:
        if pair[0] in c:
            counter += 1
        if pair[1] in c:
            counter += 1
    res[counter] += 1

for val in res:
    print(val, res[val])
    
#  ---------------------------------------------------------------------------------------------
#  solution 3
#  ---------------------------------------------------------------------------------------------
import time
import sys
import numpy as np
from io import StringIO

start = time.time()
def main():
    # input = open("/Users/prasoondwivedi/PycharmProjects/ProgrammingForEngineers/Homeworks/5CoopPairs/datapub/pub10.in", "r")
    input = sys.stdin

    input = input.read().split('\n', 1)[1]

    c = StringIO(input)  # make matrix from text input without first line
    fieldMatrix = np.loadtxt(c, dtype='int')
    rows, cols = fieldMatrix.shape[0], fieldMatrix.shape[1]

    coopPairs = []
    for x in range(0, rows):
        for y in range(0, cols):
            if fieldMatrix[x][y] == 1:      # detect robot

                for vpair in range(x + 1, rows):    # vertical searching
                    if fieldMatrix[vpair][y] == 2: break    # break if obstacle in same column
                    else:
                        if fieldMatrix[vpair][y] == 1:      # find cooperation pair
                            coopPairs.append([x, y])
                            coopPairs.append( [vpair, y])
                            break

                for hpair in range(y + 1, cols):    # horizontal searching
                    if fieldMatrix[x][hpair] == 2: break    # break if obstacle in same row
                    else:
                        if fieldMatrix[x][hpair] == 1:      # find cooperation pair
                            coopPairs.append([x, y])
                            coopPairs.append([x, hpair])
                            break
    coopPairs1 = []

    # print(coopPairs)
    for i in range(0, len(coopPairs), 2):
        coopPairs1.append(coopPairs.count(coopPairs[i]) + coopPairs.count(coopPairs[i + 1]))

    for i in range(2, 8 + 1):
        print(str(i), str(coopPairs1.count(i)))
main()

# end = time.time()
# print("time:", end - start, "s ")


#  ---------------------------------------------------------------------------------------------
#  solution 4
#  ---------------------------------------------------------------------------------------------
import time

a  = []



t1 = time.time()
M, N = map(int, input().split())
for i in range(M):
    row = list( map( int, input().split() ) )
    a.append(row)

e = [[] for _ in range(M*N)]

# hor edges
for i in range(M):
    inEdge = False
    lastj = -1
    for j in range(N):
        if a[i][j] == 2:
            inEdge = False; continue
        if a[i][j] == 1:
            if inEdge: # edge found
                e[i*N+lastj].append(i*N+j)
                e[i*N+j].append(i*N+lastj)
            else:
                inEdge = True
            lastj = j
# ver edges
for j in range(N):
    inEdge = False
    lasti = -1
    for i in range(M):
        if a[i][j] == 2:
            inEdge = False; continue
        if a[i][j] == 1:
            if inEdge: # edge found
                e[lasti*N+j].append(i*N+j)
                e[i*N+j].append(lasti*N+j)
            else:
                inEdge = True
            lasti = i

# compute edge statistics:
hist = [0]*9
for i in range(M*N-1):
    for neigh in e[i]:
        if neigh > i:
            hist[len(e[i])+len(e[neigh])] += 1

for k in range(2,9):
    print( k, hist[k])

====== Secure Matrix Areas ====== [[https://cw.felk.cvut.cz/brute/data/ae/release/2019l_be5b33pge/pge19/evaluation/input.php?task=secure|problem description]]


#  ---------------------------------------------------------------------------------------------
#  solution 1
#  ---------------------------------------------------------------------------------------------
# gets input
firstline = input().split()
M = int(firstline[0])
N = int(firstline[1])
#creates matrix
matrix = []
size = {}
upper_left = []
for i in range(M):
    row = input().split()
    matrix.append(row)

#search for secure area
def secure_area(start):
    val = []
    y, x = start[0], start[1]
    loop = min(M-y, N-x)
    cells = 1
    for k in range(1, loop):
        if cells > 3: break

        for g in range(0, k):
            if cells > 3: break
            if matrix[y+g][x+k] == '1':
                cells += 1
            if matrix[y+k][x+g] == '1':
                cells += 1
        if matrix[y+k][x+k] == '1':
            cells += 1

        if cells == 3:
            val.append(k+1)
    return val

for y in range(M-1):
        for x in range(N-1):
            if matrix[y][x] == '1':
                area = secure_area([y, x])
                # print(area)
                upper_left.append(area)
                for h in area:
                    if h in size:
                        cs = size[h]
                        size[h] = cs + 1
                    else:
                        size[h] = 1

key = list(size.keys())
# print(size)
if None in key:
    key.remove(None)
keys = sorted(key) #ascending order
for s in keys:
    if s > 1:
        print(s, size[s])

#  ---------------------------------------------------------------------------------------------
#  solution 2
#  ---------------------------------------------------------------------------------------------
import time

mx = []
M, N = 0, 0
hist = []

def checkL( ii, jj, len):

    global mx
    count = 0
    for j in range(jj, jj+len):
        if mx[ii][j] == 1:
            count += 1
    rightJ = jj+len-1

    for i in range(ii-len+1, ii):
        if mx[i][rightJ] == 1:
            count += 1
    return count

def checkArea( i1, j1 ):
    global N, hist
    size = 1
    count = 1
    while True:
        size += 1
        ii = i1+size-1
        # check boundaries
        if ii >= M: return
        if j1+size-1 >= N: return
        count += checkL( ii, j1, size )
        if count < 3: continue
        if count == 3:
            hist[size] += 1
            #print("found at", i1, j1, size)
        else: return


def histo():
    global mx, M, N, hist
    for i in range(M):
        for j in range(N):
            if mx[i][j] == 1:
                checkArea(i, j)
    return hist


t1 = time.time()
#load
M, N = map(int, input().split())
for i in range(M):
    row =  list( map( int, input().split() ) )
    mx.append(row)

hist = [0] *( max(M,N)+1 )
histo()

for i in range( len(hist)):
    if hist[i] > 0:
        print(i, hist[i])


#  ---------------------------------------------------------------------------------------------
#  solution 3
#  ---------------------------------------------------------------------------------------------
# loading from Input
M, N = input().split(" ")
M, N = [int(M), int(N)]
matrix = []
for row in range(M):
    matrix.append(list(map(int, input().split())))
secure_dict = {}
for i in range(max(M, N)):
    secure_dict[i] = 0
checked = []

def checkForSecureCells(cell, matrix, M, N, secure_dict):
    cell_x = cell[0]
    cell_y = cell[1]
    secureCells = 1
    while True:
        # placing new reference point
        if cell[0] + 1 < M and cell[1] + 1 < N:
            cell[0] += 1
            cell[1] += 1
        else:
            return
        # checking diag.
        if matrix[cell[0]][cell[1]] == 1:
            secureCells += 1
        # checking upwards
        for i in range(cell[0] - 1, cell_x - 1, -1):
            if matrix[i][cell[1]] == 1:
                secureCells += 1
        # checking leftwards
        for i in range(cell[1] - 1, cell_y - 1, -1):
            if matrix[cell[0]][i] == 1:
                secureCells += 1
        if secureCells > 3:
            return
        if secureCells == 3:
            s = (cell[0] - cell_x) + 1
            secure_dict[s] += 1
def solve():
    for row in range(M):
        for col in range(N):
            if matrix[row][col] == 1:
                checkForSecureCells([row, col], matrix, M, N, secure_dict)
    for i in secure_dict:
        if secure_dict[i] != 0 and i != 0:
            print(i, secure_dict[i])
solve()


#  ---------------------------------------------------------------------------------------------
#  solution 4
#  ---------------------------------------------------------------------------------------------
def check_for_secure(y, x, M, N, matrix):
    r = []
    c = 1  # cells with x
    n = min(M - y, N - x)
    for k in range(1, n):

        if matrix[y+k][x+k] == '1':
            c += 1

        for g in range(0, k):
            if matrix[y+g][x+k] == '1':
                c += 1
            if matrix[y+k][x+g] == '1':
                c += 1

            if c > 3: break
        if c > 3: break
        if c == 3:
            r.append(k+1)
    return r


def main():
    finput = input().split()
    M, N = int(finput[0]), int(finput[1])

    matrix, dictf = [], {}
    for i in range(M):
        row = input().split()
        matrix.append(row)

    for y in range(M-1):
            for x in range(N-1):
                if matrix[y][x] == '1':
                    area = check_for_secure(y, x, M, N, matrix)
                    if None in area: area.remove(None)
                    for h in area:
                        if h not in dictf: dictf[h] = 1
                        else:
                            cs = dictf[h]
                            dictf[h] = cs + 1
    d = list(dictf.keys())
    # if None in d: d.remove(None)
    dd = sorted(d)
    for s in dd:
        if s > 1:
            print(s, dictf[s])
            
main()