22694_Max'skingdo

Max is the king of the universe, he rules billions of planets. In each planet, there may be several residents. Residents of Max's kingdom will never die, so some of them may be as old as the universe (It is a magic world, isn't it? ). One day, Max wants to know how intellegent his people are so that he collects the intellegence information of all residents throughout universe. The intellegence can be presented by integer under a standard decided by Max. (That means, if the intellegence of resident Bob is presented as 10000, Bob is much more intellgent than the stadard. And if Max's intellegence number is 0, Max is as intellegent as the standard.) Actually, Max just cares how intellegent each planet is. To decide the intellegent degree of one planet, Max will take the middle one from all intellegent numbers of that planet and make it as the criteria. Here is the method to pick up the middle one: Supposed there are n residents in planet i. The intellegence of them are a₁, a₂, ..., a_n ( a₁ ≤ a₂ ≤ a₃ ... ≤ a_n ). If n is odd, then the middle one is a[(n+1)/2], otherwise, middle one equals (a[n/2] + a[n/2 + 1]) / 2 (Here character / means integer division, e.g. 3/2 = 1, 4/2 = 2). Since there are too many residents to process, now is your task to tell Max how smart his people are.

For each data set, there is one integer, n ( 1 ≤ n ≤ 1 000 000 ) the number of residents, in first line. Then comes n lines, each line i has two integers: p, a  ( 1 ≤ p < 1.5*10⁹,  |a| ≤  1.5*10⁹ ) which means that resident i comes from planet p and his/her intellegent number is a.

Input is terminated by EOF.

For each test data set, one output data set should be generated as follow:

For each planet p appears in the test data set, output one line presenting two integers: p which is the planet identifier from input and the middle one number described as above. Output data set should be sorted by planet identifier in ascending order.

3
2 10
1 5
2 15
2
1 2
3 4

1 5
2 12
1 2
3 4