Przełącznik

Każdy komputer w sieci ma swój unikatowy adres IP, składający się z czterech liczb z zakresu 0-255, rozdzielonych kropkami (np. 192.168.1.137). Komputery w sieci komunikują się przy pomocy pakietów. Każdy pakiet przechowuje zarówno adres nadawcy, jak i odbiorcy. Pakiety mogą być adresowane do pojedyńczych komputerów jak i do grupy komputerów. Służą do tego adresy rozgłoszeniowe: jest to adres, którego 1, 2, 3 lub 4 ostatnie liczby są równe 255, i oznacza on, że adresatem są wszystkie komputery, których pierwsza część adresu (liczby różne od 255) jest taka sama jak pierwsza część adresu rozgłoszeniowego. Np. pakiet wysłany na adres 192.168.255.255 powinien trafić do komputerów o adresach 192.168.1.1, 192.168.1.2, 192.168.2.1 ale do komputera o adresie 192.167.1.1 trafić nie powinien (jeżeli adres komputera wysyłającego pakiet na adres rozgłoszeniowy także "pasuje" do tego adresu, również powinien go otrzymać). Żaden komputer w adresie nie może posiadać liczby 255 (w szczególności adres rozgłoszeniowy nie może być adresem komputera).

Przełącznik (switch) jest urządzeniem służącym do łączenia sieci komputerowych i komputerów. Posiada on pewną liczbę portów, a do każdego z nich może być podłączona praktycznie dowolna liczba komputerów (np. poprzez inne przełączniki). Zadaniem przełącznika jest przekazywanie pakietów pomiędzy sieciami podłączonymi do różnych portów. Np. otrzymując pakiet zaadresowany do 192.168.1.1 i wiedząc, że komputer z takim adresem jest podłączony do portu nr 5, przełącznik powinien wysłać ów pakiet na ten port. (W rzeczywistości przełączniki pracują na adresach MAC a nie adresach IP).
Przełącznik nie jest konfigurowany - musi sam nauczyć się, do których portów podłączone są jakie adresy. Robi to przez obserwację. Otrzymując pakiet wysłany przez komputer o adresie 10.0.0.1 przez port nr 9 wie, że od tego momentu pakiety do 10.0.0.1 musi kierować na port 9. Ponieważ sieć może mieć strukturę dynamiczną, może wystąpić sytuacja, że po pewnym czasie przełącznik otrzyma pakiet od 10.0.0.1 na porcie 32 - wówczas musi zmienić przypisanie i pakiety do 10.0.0.1 kierować na port 32. W sytuacji, gdy adresat nie jest znany (przełącznik nie wie, na który port przesłać pakiet) odsyła komputerowi informację o niemożności znalezienia adresata.

Zadanie polega na implementacji algorytmu działania przełącznika. Informacje o portach, na które należy wysyłać pakiety na dany adres należy przechowywać w drzewie TRIE, w którym literami są kolejne liczby adresu komputera (drzewo zatem będzie miało wysokość równą 4).
Wejście i wyjście

Na wejściu programu pojawi się ciąg pakietów (każdy w osobnej linii) w postaci:
nr_portu adres_nadawcy adres_odbiorcy dana
gdzie nr_portu jest liczbą całkowitą z przedziału 0-127, oba adresy składają się z czterech liczb całkowitych z zakresu 0-255 rozdzielonych kropkami, zaś dana jest liczbą całkowitą typu int. Na każdy pakiet program powinien odpowiedzieć odpowiednim działaniem (każde w osobnej linii):

    napisem drop w przypadku, gdy nie wiadomo, na który port wysłać pakiet
    liczbami
    nr_portu dana
    w przypadku, gdy odebrany pakiet należy przesłać na port nr_portu i adres odbiorcy jest adresem pojedyńczego komputera (dana to dana z przesyłanego pakietu)
    liczbami
    nr_portu1 nr_portu2 ... nr_portuk dana
    w przypadku, gdy adres odbiorcy jest adresem rozgłoszeniowym, gdzie nr_portui to numery portów, na które trzeba wysłać pakiet, aby trafił do wszystkich znanych odbiorców "pasujących" do adresu rozgłoszeniowego (dana to dana z przesyłanego pakietu); numery portów powinny być uporządkowane rosnąco; gdy nie jest znany żaden odpowiedni odbiorca, zamiast tego program powinien odpowiedzieć napisem drop

Przykład

Wejście:
0 10.0.0.1 10.0.0.2 1
1 10.0.0.2 10.255.255.255 2
0 10.0.0.1 10.0.0.2 3
1 10.0.0.2 10.255.255.255 4
2 192.168.1.1 10.0.0.255 5
10 10.0.0.1 192.168.1.1 6
2 192.168.1.1 10.0.255.255 7
7 192.168.1.1 10.0.0.4 8
10 10.0.0.1 192.168.1.1 9

Wyjście:
drop
0 1 2
1 3
0 1 4
0 1 5
2 6
1 10 7
drop