Zadanie : drkop-4
Zadanie

Bajlandzki producent luksusowych samochodów Bararri sprzedaje swoje pojazdy w ramach przetargów. Aktualnie ma do sprzedania n samochodów. Do przetargu przystąpiło n potencjalnych nabywców, z których każdy złożył sprzedawcy ofertę kupna podając cenę jaką skłonny jest zapłacić za najnowszy model Bararri.

Codziennie w południe Barrari sprzedaje jeden samochód temu klientowi, który zaoferował najwyższą cenę - jeśli dwóch lub więcej klientów zaoferowało taką samą najwyższą cenę, to samochód sprzedawany jest klientowi z najniższym numerem.
Nabywca pojazdu przestaje być uczestnikiem przetargu od następnego dnia, zaś pozostali klienci, którzy nie mieli szczęścia stają do przetargu w dniu kolejnym z taką samą ofertą cenową z jaka startowali dnia poprzedniego.

Jednak codziennie rano przed wyborem najkorzystniejszej oferty zakupu firma losuje szczęśliwca, który może w tym dniu zmienić swoją ofertę cenową. Po wykonanej zmianie następuje rozstrzygnięcie przetargu i wyłonienie klienta, który w tym dniu zostanie szczęśliwym nabywcą pojazdu.

Napisz program, który znając oferty początkowe oraz korekty ofert z poszczególnych kolejnych dni wyznaczy numery klientów, którzy w kolejnych dniach zostaną nabywcami pojazdów.

Wejście

Pierwszy wiersz wejścia zawiera liczbę całkowitą n z zakresu 1..200000, która jest ilością oferowanych do sprzedaży samochodów.
W każdym z kolejnych n wierszy zapisano jedną liczbę całkowitą z zakresu 1..4*106 - ofertę początkową klienta - pierwsza z tych liczb jest ofertą klienta o numerze 1, druga klienta o numerze 2, itd.

W każdym z kolejnych n wierszy zapisano dwie liczby całkowite x i y. Liczba x jest numerem klienta, zaś liczba y nową ofertą cenową tego klienta z zakresu 1..4*106.

Wyjście

W kolejnych wierszach wyjścia, dla każdej pary liczb x i y należy wypisać numer klienta, który nabędzie samochód i kwotę za jaką go zakupi.

Przykład

Dla danych podanych na wejściu:

5
1
12
6
6
18
1 9
1 17
3 5
3 8
4 16

Poprawną odpowiedzią jest wyjście:

5 18
1 17
2 12
3 8
4 16

Jeśli chcesz zobaczyć inny przykład odśwież tę stronę klawiszem F5

Opcje zadania:

Biblioteki         : iostream iomanip cmath 
Limit czasu        : 0.75 s
Limit pamięci      : 96 MB
Słowa niedozwolone :