FRAKTAL - konkurs programistyczny

W barze "U Bajtosia" jest zawsze tłoczno. Zawsze wszystkie miejsca są zajęte. Oprocz miłej obsługi jest dobre piwo oraz świetna atmosfera. Właściciel baru - Bajtomił, postanowił, że nowoprzybyli goście nie będą długo czekać na miejsce do siedzenia. Z tego powodu opracował algorytm. Każdemu klientowi nadał pewną liczbę. Jeśli dana osoba za bardzo wyrożnia się wśród tłumu, tzn. że np. za mocno upija się lub awanturuje, to taka osoba dostawała odpowiednio dużą liczbę - nawet 10⁹, natomiast klient, który mało zamawiał (czasami w ogóle) i tylko zajmował miejsce, dostawał przyporządkowaną odpowienio małą liczbę - mogło to być nawet 1. Każda nadana liczba dla klienta jest unikatowa. Każdych dwóch nowych klientów, którzy nie mają miejsca, właściciel baru wymienia na dwóch takich, którzy mieli nadaną najmniejszą i największą wartość, grzecznie ich wypraszając z baru :).

Twoim zadaniem jest napisanie programu, który określi imiona klientów, którzy powinni być "wymienieni" na nowych.

Wejście

W pierwszym wierszu jedna liczba n określająca liczbę miejsc w barze "U Bajtosia". Jest to liczba mieszcząca się w przedziale [2..100 000].

Następnie n wierszy z danymi klientów, którzy zajmują miejsca - imię oraz nadana mu liczba. Imie składa się wyłącznie z dużych liter języka łącińskiego, a ilość znaków w imieniu zawiera się w przedziale [3..12].

W kolejnym wierszu jedna liczba q określająca liczbę wymian - nie więcej niż 100 000. Każda wymiana składa się z dwóch wierszy. W każdym wierszu znajduje się imię oraz nadana liczba nowego klienta (specyfikacja jak wyżej).

Wyjście

Dla każdego zapytania imiona klientów (najpierw ten o niższej nadanej wartości) zapisane w jednym wierszu, którzy będą musieli opuścić bar, a w ich miejsce usiądą dwaj nowi podani na wejściu.

Przykład

Wejście:
5
JAN 3
ROBERT 4
ANDRZEJ 5
MONIKA 10
KINGA 2
2
ROBERT 7
HUBERT 11
IWONA 1
KAMILA 9

Wyjście:
KINGA MONIKA
JAN HUBERT