#!/usr/bin/env python3

# Modul k vypsání času ve standardním formátu HH:MM:SS
from time import strftime, gmtime

# Načtení vstupu:
k, n = map(int, input().split())
# Časový rozpis ukládáme v listu tuplů tvaru (čas, tramvaj (což je int)).
# Čas ale ukládáme jako int představující počet sekund od půlnoci.
# `line_to_tuple` ze vstupního řádku udělá přímo takový tuple.
def line_to_tuple(line):
    time_string, tram = line.split()
    h, m, s = map(int, time_string.split(':'))
    return (h * 60 * 60 + m * 60 + s, int(tram))
schedule = [line_to_tuple(input()) for _ in range(n)]

# Protože pravý kraj našeho okénka může sahat až do příštího dne, musíme počítat s indexy nad `n`.
def tuple_from_schedule(idx):
    if idx >= n:
        # V takovém případě jako čas odjezdu vracíme 24 hodin + počet sekund v příštím dni.
        # Takový přístup nefunguje, pokud se v danou noc přechází na zimní/letní čas :D.
        # (A samozřejmě ani tehdy, když by příští den měl jiný rozpis, než tento)
        s, tram = schedule[idx % n]
        return (24 * 60 * 60 + s, tram)
    else:
        return schedule[idx]
# Čas (počet sekund od půlnoci) odjezdu tramvaje, která je v rozvrhu na pozici `idx`
def time_from_schedule(idx):
    return tuple_from_schedule(idx)[0]
# Číslo tramvaje, která je v rozvrhu na pozici `idx`
def tram_from_schedule(idx):
    return tuple_from_schedule(idx)[1]

# Kolik různých tramvajových linek jede během aktuálního okénka
unique_count = 0
# Hash mapa ukládájící, kolikrát v aktuálním okénku jede linka s daným číslem.
# Díky této hash mapě jsme schopni upravovat `unique_count`.
tram_dict = {}
# Ukazatele na levý a pravý kraj našeho okénka
# Pravý okraj inicializujeme na `-1`, protože okénko začíná prázdné (a ne obsahující první (tj. nultou) tramvaj).
p1, p2 = 0, -1

# Délka a začátek (index tramvaje v rozpisu) aktuálně nejkratšího okna s odjezdy všech linek
# (inicializujeme na celý den)
opt_seconds, opt_start_idx = 24 * 60 * 60, 0

while p1 < n:
    if p2 > 2*n:
        # Pokud druhý ukazatel překročí 2*n, znamená to, že se nepodařilo najít
        # žádné okénko, kdy jedou všechny tramvaje,
        print("Některá tramvajová linka během dne nikdy nejede. Neplatné zadání!")
        exit(1)
    if unique_count == k:
        # Během aktuálního časového okénka mají odjezd všechny tramvajové linky. Zaznamenej okénko, pokud je nejkratěí.
        current_seconds = time_from_schedule(p2) - time_from_schedule(p1)
        if current_seconds < opt_seconds:
            opt_seconds, opt_start_idx = current_seconds, p1
        # Pohni levým ukazatelem na další záznam.
        lost_tram = tram_from_schedule(p1)
        tram_dict[lost_tram] -= 1
        if tram_dict[lost_tram] == 0:
            # Tramvaj, kterou odebíráme z okénka, byla jediná své linky, která v okénku byla.
            unique_count -= 1
        p1 += 1
    elif unique_count < k:
        # Ne všechny linky mají odjezd v aktuálním okénku. Posuň pravý ukazatel.
        p2 += 1
        new_tram = tram_from_schedule(p2)
        tram_dict[new_tram] = 1 if new_tram not in tram_dict else tram_dict[new_tram] + 1
        if tram_dict[new_tram] == 1:
            # Posunutím ukazatele jsme získali odjezd linky, která zatím během okénka nejela.
            unique_count += 1
    else:
        # Případ `unique_count > k` nikdy nenastane.
        print("CHYBA V SOLVERU.")
        exit(1)

# Vypiš nalezené optimum
formatted_start = strftime("%H:%M:%S", gmtime(time_from_schedule(opt_start_idx)))
print(f"{formatted_start} {opt_seconds}")