题目描述

Max 是宇宙之王，他统治着很多星球。每个星球上都有一些居民。 Max 王国中的居民是不会死的，其中有一些居民跟宇宙一样古老（真是一个魔幻的世界，不是吗？）。一天， Max 想知道他的人民究竟有多么聪明，以此来收集宇宙中居民的智商水平信息。

智商水平能根据 Max 制定的一个标准来衡量（也就是说，如果 Bob 的智商值是 10000 ，那么 Bob 比标准的智商值要高出 10000 。又如果 Bob 的智商值是 0 ，那么 Bob 就则好达到了标准的智商水平）。

实际上， Max 只想知道每个星球究竟有多么聪明。为了评估一个星球的智商度， Max 会取该星球所有居民的智商的中间值作为衡量标准。例如，如果 i 星球有 n 个居民，他们的智商值分别是 $a_1,a_2,...,a_n$ ( $a_1$ <= $a_2$ <= $a_3$... <= $a_n$ )。如果 n 是奇数，则中间值是 a[(n+1)/2]，否则为 (a[n/2]+a[n/2+1])/2 （这里的除法使用的是整数除法，如 3/2=1 , 4/2=2 ）。由于有太多的居民，现在你的任务是告诉 Max 每个星球的智商度。

输入格式

第 1 行一个整数 n ( 1 <= n <= 100000 )，表示有 n 条信息。

接下来 n 行，每行包含两个整数 p , a ( 1 <= p < 1.5*${10}^9$ , |a|<=1.5*${10}^9$ )，表示在星球 p 里有一个居民的智商值为 a 。

输出格式

输出若干行，包括输入信息里出现过的所有星球，每行两个整数 p , q ，表示星球 p 的智商度为 p 。

样例

3
2 10
1 5
2 15

1 5
2 12