A Choice at the Crossroads

Interview

Time limit1sMemory limit512 MB

Summary

Given N miniatures with quality and price, find the two picks under each rule: highest quality (ties by lowest price), and lowest price (ties by highest quality).

Level: Easy2 of 10
Topics: Array, Implementation
Solved: No attempts yet

Problem

Photo of Chokseongnu

[Photo] Chokseongnu

Quality or price, that is the question..

Boseon, who came to Jinju for an outing, decided to buy a Chokseongnu miniature as a souvenir. Chokseongnu is a pavilion in Jinju Fortress and is designated as a Gyeongsangnam-do Tangible Cultural Property. It served as the southern command post of the fortress, and it is well known as the place where Nongae died a martyr's death at Uiam rock in front of the pavilion.

Boseon went to the souvenir shop to buy a Chokseongnu miniature and was astonished. The shop displayed Chokseongnu miniatures of every kind. Each one was carefully made by an artisan, so quality and price varied widely, and no two miniatures had the same quality and the same price. Seeing all of them, Boseon nearly lost control of the urge to buy, but calmed down and decided to buy only two. Boseon decided to pick the miniatures in two ways, as follows.

From the miniatures on display, pick the one with the highest quality and bring it. If there are several such miniatures, pick the one with the lowest price. Repeating this process twice is the first method.
From the miniatures on display, pick the one with the lowest price and bring it. If there are several such miniatures, pick the one with the highest quality. Repeating this process twice is the second method.

Find out which miniatures Boseon picks under each method.

Input

The first line gives the number of Chokseongnu miniatures on display in the souvenir shop, $N$ . $(2 \le N \le 100\,000)$

From the second line, the next $N$ lines give the quality $Q_i$ and the price $P_i$ of the $i$ -th miniature type on display, separated by a space. $(1 \le Q_i, P_i \le 10\,000)$

All numbers in the input are integers.

Output

The first line prints the quality and price of the first miniature picked, then the quality and price of the second miniature picked, separated by spaces, in order, when the first method is used.

The second line prints the same for the second method.

The result of the first method does not affect the result of the second method.

Examples1

Example 1
Input
```
4
3 1
2 2
2 3
1 1
```
Expected output
```
3 1 2 2
3 1 1 1
```