Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

FR_09_20 - U "Bajtosia"

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 109, 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

Dodane przez:Marcin Kasprowicz
Data dodania:2018-05-25
Limit czasu wykonania programu:1s-3s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: ASM32-GCC COBOL D-CLANG D-DMD ELIXIR FANTOM GOSU GRV JS-MONKEY NIM OBJC OBJC-CLANG PICO RUST SCM qobi CHICKEN VB.NET

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.