题目背景

新学期开始，大维老师想通过合理分配同桌组合来促进男女同学互帮互助，让大家在学习中更快进步。

题目描述

大维老师的班级里有 $n$ 个男生和 $n$ 个女生，需要两两配对成 $n$ 对同桌。大维老师收集了每个同学的平均成绩，第 $i$ 个男生的成绩为 $b_i$ ，第 $i$ 个女生的成绩为 $g_i$ 。

如果第 $i$ 个男生和第 $j$ 个女生组成同桌，那么这一对同桌的成绩为

b_i + g_j.

在完成所有 $n$ 对同桌分配后，成绩最高的那一对同桌的成绩被称为该方案的“分配度”。大维老师认为，分配度越小越好。现在对于每个 $k=1,2,\dots,n$ ，请计算在仅考虑前 $k$ 名男生和前 $k$ 名女生时，能达到的最小分配度。

第一行包含一个整数 $n$ ，表示男女生人数。
接下来 $n$ 行，每行包含两个整数 $b_i$ 和 $g_i$ ，分别表示第 $i$ 个男生和第 $i$ 个女生的成绩。

输出共 $n$ 行，第 $k$ 行表示当只考虑前 $k$ 名男生和前 $k$ 名女生时，最小的分配度。

10
10
9

当 $k=1$ 时，只有第 1 名男生（成绩为 2）和第 1 名女生（成绩为 8），唯一分配度为 $2+8=10$ 。
当 $k=2$ 时，男生成绩为 $\{2,3\}$ ，女生成绩为 $\{8,1\}$ ，最优配对方案可为 $(2,8)$ 和 $(3,1)$ ，分配度为 $\max(2+8,3+1)=10$ 。
当 $k=3$ 时，男生成绩为 $\{2,3,1\}$ ，女生成绩为 $\{8,1,4\}$ ，最优方案可为 $(1,8),(2,1),(3,4)$ ，分配度为 $\max(1+8,2+1,3+4)=9$ 。