W końcu Ci się poszczęściło. Zaczynasz pracę w dużej renomowanej firmie. Ktoś docenił twoje ponadprzeciętne zdolności i teraz masz okazję się wykazać. Już nie możesz się doczekać swojego pierwszego zadania.

Podążasz za kierownikiem, który prowadzi Cię do korytarza pełnego drzwi. Dostajesz kartkę papieru i jedyne, co słyszysz od swojego nowego przełożonego zanim zniknie w jednym z pomieszczeń: "Masz tu listę zaplanowanych meetingów na najbliższy tydzień. Poukładaj je tak, żeby jak najwięcej z nich się odbyło!".

Jesteś w stanie to zrobić?

Wejście

Na wejściu pojawi się d (0 < d ≤ 1000), oznaczające liczbę dni do opracowania. Każdy dzień opisany jest następująco: najpierw liczba dostępnych pomieszczeń p (0 < p ≤ 10⁵) i zaplanowanych spotkań s (0 < s < 10⁶). Następnie s linii opisujących spotkania. Pojedyncze spotkanie to cztery wartości: rg:rm, zg:zm (0 ≤ rg, zg ≤ 23, 0 ≤ rm, zm ≤ 59), czyli godzina (w formacie godzina:minuta) rozpoczęcia i zakończenia. Żaden meeting nie zaczyna się i kończy o tej samej godzinie. Godzina rozpoczęcia jest zawsze wcześniejsza niż zakończenia. Spotkania odbywają się w obrębie jednego dnia (nie ma meetingów zaczynających się jednego dnia, a kończących następnego).

Rozmiar plików wejściowych nie przekracza 9M.

Wyjście

Dla każdego dnia musisz podać maksymalnę liczbę spotkań jaka może się odbyć oraz zaplanować przydział spotkań do salek. W następnych liniach wypisz meetingi, które odbędą się w kolejnych pomieszczeniach.

• Numeracje spotkań wyznacza kolejności pojawiania się na wejściu. Spotkania numerujemy od 1 do s.
• Spotkania nie mogę się nakładać, ale mogą się zaczynać dokładnie w momencie zakończenia poprzedniego.
• Jeżeli meetingi da się przydzielić do salek na kilka sposobów, wypisz dowolny z nich (spotkania przypisane do danego pomieszczenie można podać w dowolnej kolejności). Tutaj jest napisany własny sędzia, który sprawdza poprawność Twojego programu.
• Pokoje nie są numerowane. Jeżeli możesz użyć np. 7 z 10 salek, wypisz 7 linii.
• Po wypisaniu przydziału dla wszystkich salek w danym dniu wyświetl pustą linię (także po ostatnim).

Przykład:

Wejście:
2
2 3
11:20 12:00
11:30 11:40
11:40 11:55
3 6
17:15 18:30
17:20 19:00
17:15 18:00
16:55 17:55
17:10 18:10
17:00 18:00

Wyjście:
3
1
2 3

3
1
2
3

Uwaga: Wypisywanie pustych linii pomiędzy przydziałami do kolejnych pomieszczeń spowoduje błędną odpowiedź.