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:

11
5
14
4
18
11
14
17
2
9
12
13
9 13
6 13
1 20
5 1
6 3
3 16
6 17
5 15
11 3
8 4
11 3

Poprawną odpowiedzią jest wyjście:

4 18
7 17
1 20
2 14
9 13
3 16
6 17
5 15
10 12
8 4
11 3

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 :