aeriana

O companie aeriană are planificate $N$ zboruri. Fiecare zbor are asociate câte șase numere naturale cu următoarea semnificație: primul număr $A_1$ identifică aeroportul de decolare, cel de-al doilea număr $A_2$ identifică aeroportul de aterizare, următoarele patru numere naturale $H_1$, $M_1$, $H_2$ și $M_2$, reprezintă în ordine ora și minutul decolării, respectiv ora și minutul aterizării. Aterizarea poate să fie în ziua curentă sau în ziua următoare. Un zbor poate să dureze maximum $23$ de ore și $59$ de minute. De exemplu, pentru $H_1 = 10$, $M_1 = 5$, $H_2 = 15$, $M_2 = 20$ aterizarea are loc în aceeași zi cu decolarea (zborul durează $5$ ore și $15$ minute), iar pentru $H_1 = 23$, $M_1 = 5$, $H_2 = 1$, $M_2 = 15$ aterizarea are loc în ziua următoare (zborul durează $2$ ore și $10$ minute).

Un virus informatic s-a infiltrat în sistemele de calcul ale companiei și a inversat momentul de decolare cu cel de aterizare al zborurilor pe care le consideră speciale. Un zbor este considerat special de către acest virus în cazul în care codul aeroportului de decolare, $A_1$, este un număr prim, iar codul aeroportului de aterizare, $A_2$, se divide cu suma cifrelor lui $A_1$.

Cerințe

Cunoscându-se numărul de zboruri $N$ și datele fiecăruia, înainte de intervenția virusului, să se determine:

1. Care este durata maximă a unui zbor, înainte de intervenția virusului.
2. Care este durata maximă a unui zbor, după intervenția virusului. Se iau în calcul atât duratele zborurilor inversate (speciale), cât și duratele zborurilor neinversate (nespeciale).

Date de intrare

Fișierul aeriana.in conține pe prima linie valoarea $C$ (numărul cerinței, poate fi $1$ sau $2$), pe a doua linie valoarea $N$ (numărul de zboruri). Pe fiecare dintre următoarele $N$ linii sunt câte șase numere naturale $A_1$, $A_2$, $H_1$, $M_1$, $H_2$, $M_2$, în această ordine, despărțite prin câte un spațiu, cu semnificația din enunț.

Date de ieșire

Fișierul aeriana.out va conține pe prima linie două numere naturale separate printr-un spațiu, reprezentând numărul de ore și respectiv numărul de minute ale zborului de durată maximă, în condițiile cerinței specificate.

Restricții și precizări

• $1 \leq N \leq 1 \ 000$;
• $0 \leq H_1, H_2 \leq 23$;
• $0 \leq M_1, M_2 \leq 59$;
• $0 \leq A_1, A_2 \leq 1 \ 000 \ 000 \ 000$;
• Un zbor va dura cel puțin un minut și cel mult $23$ de ore și $59$ de minute;
• Pentru $19$ puncte, $C = 1$ și toate zborurile se desfășoară în aceeași zi;
• Pentru $17$ puncte, $C = 1$, $M_1 = 0$, $M_2 = 0$ pentru toate zborurile;
• Pentru $17$ puncte, $C = 1$ și nu există restricții suplimentare;
• Pentru $47$ de puncte, $C = 2$.

Exemplul 1

aeriana.in

1
3
47 55 0 0 23 59
1 437 23 43 10 34
11 457 10 43 10 23

aeriana.out

23 59

Explicație

$C = 1$, $N = 3$. Duratele acestor zboruri sunt, în ordine, $23$ de ore și $59$ de minute, $10$ ore și $51$ de minute, iar pentru ultimul zbor, $23$ de ore și $40$ de minute.

Exemplul 2

aeriana.in

2
3
47 55 0 0 23 59
1 437 23 43 10 34
11 457 10 43 10 23

aeriana.out

23 40

Explicație

$C = 2$, $N = 3$. Pentru primul zbor $A_1 = 47$ este număr prim, suma cifrelor sale este egală cu $11$ și $A_2 = 55$ se divide cu $11$, deci primul zbor devine 23 : 59 − 00 : 00 și are o durata de $0$ ore și $1$ minut. Al doilea zbor rămâne nemodificat, deoarece $1$ nu e prim. Al treilea zbor rămâne nemodificat. Chiar dacă $11$ este prim, $457$ nu se divide cu $2$ (suma cifrelor lui $11$). Zborul de durata maximă, dupa interventia virusului, este cel de-al treilea.