선택의 기로

[사진] 촉석루

품질이냐 가격이냐, 그것이 문제로다..

진주 나들이를 온 보선이는 기념품으로 촉석루 미니어처를 사기로 했다. 촉석루는 진주성에 있는 누각이며 경상남도 유형문화재 중 하나로, 진주성의 남쪽 지휘대로 사용됨과 동시에 논개가 촉석루 앞 의암에서 순국한 것으로 알려져 유명한 곳이다.

촉석루 미니어처를 사려고 기념품 가게에 들른 보선이는 놀라움을 금치 못했다. 가게에는 각양각색의 촉석루 미니어처가 진열되어 있었기 때문이다. 모든 미니어처는 장인이 한 땀 한 땀 심혈을 기울여 만든 탓인지 품질과 가격이 천차만별이었고, 품질과 가격이 모두 같은 두 미니어처는 없었다. 각양각색의 미니어처를 본 보선이는 물욕이 폭발할 뻔했지만 가까스로 마음을 진정시키고, 미니어처를 두 개만 사기로 했다. 보선이는 두 가지 방법으로 미니어처를 골라보기로 했는데, 그 방법은 다음과 같다.

• 진열된 미니어처 중에서 품질이 가장 높은 것을 골라 가져온다. 그런 미니어처가 여러 개라면 가격이 가장 낮은 것을 골라 가져온다. 이 과정을 두 번 반복하는 것이 첫 번째 방법이다.
• 진열된 미니어처 중에서 가격이 가장 낮은 것을 골라 가져온다. 그런 미니어처가 여러 개라면 품질이 가장 높은 것을 골라 가져온다. 이 과정을 두 번 반복하는 것이 두 번째 방법이다.

보선이가 각 방법에 따라 미니어처를 고르게 되었을 때 어떤 미니어처를 고르게 되는지 알아보자.

첫 번째 줄에는 기념품 가게에 진열된 촉석루 미니어처의 개수 $N$이 주어진다. $(2 \le N \le 100\,000)$

두 번째 줄부터 $N$개의 줄에 걸쳐 가게에 진열된 $i$번째 미니어처 종류의 품질 $Q_i$와 가격 $P_i$가 공백으로 구분되어 주어진다. $(1 \le Q_i, P_i \le 10\,000)$

입력으로 주어지는 모든 수는 정수이다.

첫 번째 줄에는 첫 번째 방법을 선택했을 때 처음으로 고른 미니어처의 품질과 가격, 두 번째로 고른 미니어처의 품질과 가격을 공백으로 구분하여 순서대로 출력한다.

두 번째 줄에는 두 번째 방법을 선택했을 때 같은 내용을 출력한다.

첫 번째 방법의 결과는 두 번째 방법의 결과에 영향을 주지 않는다.