普及-⏱ 1000ms💾 256MB#P3201🏷️ 平衡树数据结构

题目描述

清算机连续 $n$ 天处理账单:第 $d$ 天会收到 $M_d$ 张新账单(面额为正整数), 随后机器从所有未支付的账单中选出面额最小和最大的两张同时付清 (其余账单保留到下一天)。

按天输出每天付清的两张账单面额:先小后大。 数据保证每天付款时至少有两张未支付账单。

输入格式

第一行一个正整数 $n$,为天数; 以下 $n$ 行:每行先是一个非负整数 $M$,后跟 $M$ 个正整数(小于 $10^9$),为当天收到的账单面额。

输出格式

共 $n$ 行,每行两个整数:当天支付的最小面额与最大面额,用空格分开。

数据范围

$$n \le 15000$$
,每天 $M \le 100$$,面额 $< 10^9$;保证每天可付两张。

样例输入 #1
4
3 3 6 5
2 8 2
3 7 1 7
0
样例输出 #1
3 6
2 8
1 7
5 7
样例输入 #2
1
2 10 20
样例输出 #2
10 20