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:

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

Poprawną odpowiedzią jest wyjście:

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

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 :