import sys
import numpy
from math import inf
from array import array
S = 16384

mapa = []
input_file = open("01.in", "rb")
for y in range(S):
    # Musíme dát pozor na endianitu (data jsou
    # little-endian) a tak načtení svěříme numpy
    numpy_radek = numpy.fromfile(
        input_file,
        dtype="<u2",  # unsigned 2bajtová čísla
        count=S       # v little-endian(<)
    )
    # Pro rychlejší přístup k prvkům převedeme
    # na interní Pythoní pole
    radek = array('H')  # minimálně 2b číslo
    radek.fromlist(numpy_radek.tolist())
    mapa.append(radek)


print("loaded")
koupene = []
useky = [(500, 0), (2000, 0), (S+1, 0)]
changed = True
while changed:
    new_useky = []
    projito = 0
    xk = 0
    while xk < S:
        projito2 = projito + 1
        while projito2 < len(useky) and useky[projito2][0] <= xk + 1000:
            projito2 += 1

        yk = min(map(lambda x: x[1], useky[projito:projito2+1]))
        if yk > S:

            xk = useky[projito+1][0]
        else:
            print(f"\rkvadrant {xk} {yk} ", end="", flush=True)
            best = (inf, (-1, -1))
            for x in range(xk, min(xk+501, S)):
                for y in range(yk, min(yk+501, S)):
                    if mapa[y][x] != 0:
                        score = mapa[y][x] - 3*(x - xk) - 1.9*(y-yk)  # 3 1.9
                        if score < best[0]:
                            best = (score, (y, x))

            if best[0] != inf:
                y, x = best[1]
                new_useky.append((x+500, y+500))
                koupene.append(best[1])
                xk = best[1][1] + 501
            else:
                new_useky.append((xk+500, yk+500))
                xk += 501

        while projito < len(useky)-1 and xk >= useky[projito+1][0]:
            projito += 1

    useky = new_useky
    useky.append((S+1, useky[-1][1]))
    if all(map(lambda x: x[1] > S, useky)):
        break


print("\nVýpis", flush=True)
f = open("DPMrizka.out", "w")
f.write(f"{len(koupene)}\n")
for dum in koupene:
    f.write(f"{dum[0]} {dum[1]}\n")
f.close()