Zadanie 4 - Odkrycie Snickersa

Szefowie wyprawy Mars Two byli bardzo przewidujący. Przewidzieli trudne warunki atmosferyczne, więc dostosowali temperaturę i nasłonecznienie w habitatach. Przewidzieli ewentualne trudności komunikacyjne, więc zapewnili odpowiednią infrastrukturę. Przewidzieli, że do codzienności będzie się wkradała nuda, więc wybudowali centra kultury, centra rozrywki, parki, zaopatrzyli każdego mieszkańca w komputery, konsole do gier, TV. Przewidzieli rodzącą się w każdym człowieku potrzebę piękna, więc sprowadzili ziemskie dzieła sztuki. Przewidzieli także, że ludzka ciekawość bywa niepohamowana, więc zapewnili możliwość wycieczki po powierzchni Marsa w nowoczesnych busołazikach o nazwie Snickers.

Właściciele habitatów ziemskich przewidzieli wszystko. No, może poza faktem, że zaledwie kilkadziesiąt kilometrów od najdalej na wschód wysuniętego habitatu znajduje się grupa innych habitatów. Bynajmniej nie ziemskich.

Uczestnicy jednej z pierwszych wycieczek Snickersem przeżyli spore zaskoczenie, gdy po około godzinie jazdy ich oczom ukazała się struktura niezbyt wysokich budowli, a tuż przed nimi chodziła grupa niedużych istot (nieco ponad metr wysokości) w czymś w rodzaju szarych kombinezonów.

W pierwszym momencie przedstawiciele obu nacji nie wykazali się dużym rozgarnięciem, bo rozbiegli się w popłochu (jak się później okazało jedni i drudzy krzyczeli "AAA! Kosmici!"). Jednak gdy minął pierwszy szok i dotarło do nich, że żadne z nich nie ma wrogich zamiarów, postanowili się ze sobą porozumieć.

Nie było to proste. Okazało się, że jako gatunki korzystamy z zupełnie innych pasm częstotliwości, przez co nie jesteśmy w stanie się nawzajem usłyszeć lub też słyszymy się tylko częściowo. Nowi przyjaciele po porozumieniu na migi zgodzili się nagrać próbki swoich wypowiedzi, które po powrocie do ziemskich habitatów zostaną przekazane do analizy. To samo zrobili ziemscy uczestnicy wycieczki. Po wymianie próbek Ziemianie zaproponowali spotkanie za 7 soli (marsjańskich dni), by porównać wyniki, po czym wszyscy udali się z powrotem do swoich domów.

Nie było to proste. Okazało się, że jako gatunki korzystamy z zupełnie innych pasm częstotliwości, przez co nie jesteśmy w stanie się nawzajem usłyszeć lub też słyszymy się tylko częściowo. Nowi przyjaciele po porozumieniu na migi zgodzili się nagrać próbki swoich wypowiedzi, które po powrocie do ziemskich habitatów zostaną przekazane do analizy. To samo zrobili ziemscy uczestnicy wycieczki. Po wymianie próbek Ziemianie zaproponowali spotkanie za 7 soli (marsjańskich dni), by porównać wyniki, po czym wszyscy udali się z powrotem do swoich domów.

Ludzcy analitycy od razu zabrali się do pracy. Zaproponowali algorytm, rozkładający dźwięk na sekwencję próbek względem pewnej składowej, którą roboczo nazwali mocą próbki, a następnie ponownie splatający je ze sobą w różnych konfiguracjach, by odseparować pewne wzorce. Pierwsza rzecz, którą chcieliby na tym etapie uzyskać, to obniżyć częstotliwość niektórych próbek. Naukowcy korzystają tutaj z pewnej teorii (jeszcze nie do końca sprawdzonej), według której jeśli próbkę o wysokiej częstotliwości niesłyszalnej dla naszego ucha (przyjmujemy, że jest to powyżej 15 kHz) zestawi się z próbką o niższej częstotliwości (lub z kilkoma takimi próbkami), to ma się wrażenie znacznego obniżenia częstotliwości pierwszej próbki. Po czymś takim moc dostawionej próbki bez względu na jej początkową wielkość zmienia się i dostosowuje do mocy pierwszej próbki. Działa to jednak tylko dla takich próbek, których częstotliwości można przez siebie podzielić bez reszty.

Teraz do pracy przystępują programiści. Analitycy zażyczyli sobie programu, który będzie odbierał od nich kolejne próbki z nagrania i rozdzielał je względem podanych mocy zachowując kolejność nadejścia. Poza tym na dowolnym etapie dodawania próbek program ma dawać analitykowi możliwość splatania próbek. Splatanie w tej fazie rozszyfrowywania języka będzie polegało na wybraniu dwóch sekwencji przez analityka. Program ma wtedy za zadanie przejrzeć pierwszą sekwencję i po każdej próbce niesłyszalnej dla ludzkiego ucha spróbować wstawić pierwszą odnalezioną próbkę z drugiej sekwencji w taki sposób, by po odtworzeniu próbek z pierwszej sekwencji przynajmniej części z nich obniżyła się częstotliwość. Przez wstawienie próbki jej moc ulega zmianie, więc musi ona zniknąć ze swojej poprzedniej sekwencji. Ponadto przez to, że musi zostać odtworzona dokładnie po próbce o wysokiej częstotliwości, zmienia się jej kolejność, a więc także położenie w czasie.

Kolejność próbek jest bardzo ważna, dlatego podczas pojedynczej operacji splatania dwóch sekwencji należy uważać na to, by zawsze wstawiać próbkę, która w swojej sekwencji pojawia się później niż ostatnio użyta.

Oczywiście dla lepszego efektu algorytmu analityk może kilka razy splatać próbki o tej samej mocy, by móc wstawić więcej próbek za niesłyszalną próbką.

Wejście:

W pierwszej linii wejścia znajduje się liczba naturalna n, określająca liczbę operacji. W kolejnych n liniach znajdą się operacje scharakteryzowane następująco:
*) 0 m f - oznacza dodanie próbki o mocy m i częstotliwości f wyrażonej w Hz, gdzie m i f są liczbami naturalnymi.
*) 1 m1 m2 - oznacza próbę splecenia próbek o mocy m1 z próbkami o mocy m2 (próbki o mocy m2 wstawiamy pomiędzy próbki o mocy m1), gdzie m1 oraz m2 są liczbami naturalnymi i m1 ≠ m2.
*) 2 m - oznacza wyświetlenie sekwencji próbek o mocy m, gdzie m jest liczbą naturalną.

1<=n<=1000000
1<=m<=100000
1<=f<=1000000

Wyjście:

Dla operacji 1 program ma wypisać liczbę próbek, które udało się wstawić. Dla operacji 2 program ma wyświetlić sekwencję wartości częstotliwości próbek o podanej mocy lub słowo "BRAK", jeśli nie ma próbek o takiej mocy.

Przykład:

Wejście:

14
0 1 10000
0 3 25000
0 1 10
0 3 20000
0 1 200
0 3 1000
0 3 100000
0 2 20000
2 3
1 3 1
2 3
2 1
1 2 1
2 2

Wyjście:

25000 20000 1000 100000
2
25000 10 20000 200 1000 100000
10000
1
20000 10000

UWAGA! Zadanie należy rozwiązać przy pomocy samodzielnej implementacji listy wskaźnikowej. Nie można używać bibliotek STL.