Połączenie posortowanych list (bez powtórzeń)

Treść zadania

Otrzymujesz M list liczb całkowitych, z których każda jest posortowana niemalejąco. Połącz je w jedną listę posortowaną rosnąco i zawierającą każdą wartość tylko raz (powtórzenia mogą występować zarówno w obrębie jednej listy, jak i między listami). Niektóre listy mogą być puste.

Dane wejściowe

• 1. linia: M — liczba list
• kolejne M linii: opis jednej listy — najpierw jej długość k, a po niej k liczb posortowanych niemalejąco (wszystko oddzielone spacjami); pusta lista to linia zawierająca samo 0

Dane wyjściowe

Jedna linia: elementy połączonej listy oddzielone spacjami. Jeśli wszystkie listy są puste, wypisz pustą linię.

Ograniczenia

• 1 ≤ M ≤ 100
• 0 ≤ k ≤ 100
• elementy list są z przedziału $[-10^6, 10^6]$

Uwagi

• Najmniejszy element wyniku to najmniejszy z pierwszych elementów list. Trzymaj w kopcu (heapq) po jednym „bieżącym” elemencie z każdej listy: zdejmuj najmniejszy, a na jego miejsce wkładaj następny element z tej samej listy. Dla $N$ elementów łącznie daje to czas $O(N \log M)$.
• Powtórzenia łatwo pominąć: wynik powstaje w kolejności rosnącej, więc wystarczy porównać nowy element z ostatnio dopisanym.

Przykład

4
4 -6 23 29 33
4 6 22 35 71
4 5 19 21 37
4 -12 -7 -3 28

-12 -7 -6 -3 5 6 19 21 22 23 28 29 33 35 37 71

Zadanie pochodzi z otwartego zbioru Nauka-Programowania (z rozwiązaniami wzorcowymi). Zgłoś błąd w treści lub testach.