AlgoLiga 2018

Nasza bohaterka ma zamiar zrobić sobie prawo jazdy, jest ambitna, więc nie che iść śladem PRK, który je kupił. Magda jeszcze nie skończyła kursu na prawo jazdy (kwestia czasu, bo niedługo skończy), więc ma szalony plan, aby spróbować pojeździć samochodem na parkingu. Znalazła bardzo duży parking, Rafał załatwił dla niej samochód (jeszcze jest on samochodem, ale nic nie wiadomo, jak będzie wyglądał w najbliższej przyszłości). Jednak gdy Rafał zobaczył na parkingu inne pojazdy, które jeszcze można nazwać samochodami, przestraszył się, wpadł na cudowny pomysł, że odgrodzi taśmą wszystkie samochody, tak, żeby Magda widziała, że nie może tam jechać (no... niby może, ale to grozi odkształceniem dwóch pojazdów, czego Rafał bardzo pragnie uniknąć).

Odgrodzenie będzie polegało na przyczepienu taśmy do samochodu, jednak Rafał chce wykorzystać jak najmniej samochodów do przyczepiania taśmy (bo potem będzie trzeba bardzo ostrożnie ją odczepić), dlatego kiedy samochody stoją w jednej linii, to do środkowych nie przyczepiamy taśmy, w odgrodzonym terenie muszą się znaleźć wszystkie samochody (tam mają większe szanse na nieodkształcenie). Jednak samochodów jest całe mnóstwo, więc jedynym rozwiązaniem jest napisanie programu, który pomoże wyznaczyć kolejność samochodów, do których należy przyczepić taśmę.

Rafał co prawda umie programować, ale nie jest to jego całe życie i nie poradzi sobie z tym problemem, nie chce też prosić Magdy o pomoc, bo ona uzna, że jest to niepotrzebne, więc poprosił Cię o pomoc. Rafał już zrobił listę położeń samochodów, położenia samochodu określa współrzędna x,y. Rafał zaczyna przyczepiać taśmę z dolnego-lewego rogu (samochód o najmniejszej współrzędnej y, a jeśli jest kilka takich, to ten, co ma najmniejszą współrzędną x), należy podać następne samochody, do których należy przyczepiać taśmę i skończyć na tym samym samochodzie. Rafał będzie przyczepiał taśmę w stronę zgodną z ruchem wskazówek zegara. Napisz jak najszybciej ten program, żeby zaoszczędzić mechanikom napraw samochodów!

Wejście:

W pierwszej linii liczba n, jest to ilość wszystkich samochodów, które mogą ulec zniszczeniu (n<=500000). Następnie w n liniach współrzędne samochodów x,y ( -5000 <= x,y <=5000) na szczęście są one tylko na środku parkingu, dzięki temu Magda ma duży obszar do jazdy.

Wyjście:

Należy wypisać w osobnych liniach współrzędne samochodów x, y.
Zaczyna od tego co jest w dolnym-lewym rogu, dalej idzie zgodnie z ruchem wskazówek zegara i kończymy na startowym. 

Example

Input:

6
1 1
2 3
3 5
4 1
2 1
3 2

Output:

1 1
3 5
4 1
1 1