题目描述

Max是宇宙之王，他统治着很多星球。每个星球上都有一些居民。一天，Max想知道他的人民究竟有多少聪明，以此来收集宇宙中居民的智商水平信息。智商水平能根据Max指定的一个标准来衡量（即，如果Bob的智商值是10000，那么Bob比标准的智商值要高出10000。又如果Bob的智商值是0，那么Bob就刚好达到了标准的智商水平）。实际上，Max只想知道每个星球究竟有多么聪明。为了评估一个星球的智商度，Max会取该星球所有居民的智商的中间值作为衡量标准。例如，如果i星球有n个居民，他们的智商值分别为a1,a2,…,an(a1<=a2<=a3<=…<=an)。如果n是奇数，则中间值是a[(n+1)/2]，否则为(a[n/2]+a[n/2+1])/2，这里的除法使用的是整数除法，如3/2=1）。由于有太多居民，现在你的任务是告诉Max每个星球的智商度。

输入要求

输入包含多组测试。对每一组测试数据，首先输入一个整数表示n（1<=n<=1 000 000），代表居民数量。接下来的n行，在第i行输入2个数据p和a（1<=p<1.5*10^9,|a|<=1.5*10^9），表示居民i来自来自p星球，其智商值为a。输入以EOF结束。

输出要求

对每一组测试数据，给出一个输出结果。对于出现在测试数据集里的某个p星球，输出一行数据，其中包含2个整数，第一个数据是表示p星球的具体编号，第二个数据就是前面描述的该星球居民的智商的中间值。输出数据将按照星球编号进行升序排序。

输入样例

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

输出样例

1 5
2 12
1 2
3 4

提示

来源

NBU OJ