AlgoLiga 2018

Tak, to już dziś! Egzamin ze "Wstępu do algorytmów". Profesor Algobit przygotował zestaw trudnych i bardzo trudnych zadań dla swoich podopiecznych. Jest on człowiekiem, który swoją wiedzę z algorytmów wykorzystuje często w życiu codziennym i jest tak też i tym razem. Oprócz egzaminu, studenci muszą się stawić na odpowiednią godzinę, która nie jest przedstawiona wprost. 

Przed egzaminem, profesor postawił kilka warunków, do których uczniowie muszą się dostosować. Oto one:

• każdy student wybiera sam długość czasu, w jakim chce pisać egzamin. Im krótszy czas, tym łagodniej będzie oceniany
• zdający wchodzą według listy w dzienniku
• na egzamin wchodzi maksymalnie tyle osób, ile jest miejsc na sali
• egzamin rozpoczyna się o tej samej godzinie dla wszystkich uczestników danej grupy. Studenci, którzy zadeklarowali krótszy czas na pisanie egzaminu odkładają długopisy i grzecznie czekają, aż wszyscy z sali skończą pisać. 
• gdy skończy pisać ostatnia osoba z danej grupy, na salę wchodzą następne osoby (czas zamiany grup jest pomijalnie mały)

Profesor jest osobą, która bardzo szanuje swój czas, dlatego też znając czasy pisania egzaminu kolejnych studentów dobiera tak grupy, aby całkowity czas był najkrótszy.

Twoim zadaniem nie jest zdanie tego egzaminu, tylko określenie godziny, w której on się skończy.

Uwaga! Egzamin może trwać wiele dni ale nas interesuje tylko godzina jego zakończenia. Rozpatrujemy format 24 godzinny.

Wejście

W pierwszym wierszu jedna liczba t określająca ilość zestawów danych (t < 1000).

Dla każdego zestawu danych:

Najpierw dwie liczby s i n określające odpowiednio ilość studentów na liście oraz pojemność sali (0 < s ≤ 100000, 0 < n < 1000) i godzina rozpoczęcia egzaminu w formacie hh:mm np. 08:30.

W drugim wierszu każdego zestawu s liczb naturalnych dodatnich nie większych niż 1000, określających zadeklarowane czasy (w minutach) na egzamin przez kolejnych studentów.

Wyjście

Dla każdego zestawu godzina zakończenia egzaminu w formacie: gg:mm 

Przykład

Wejście:
1
7 2 08:00
5 6 4 3 6 7 8

Wyjście:
08:24