题目描述

Mirko 和 Slavko 正在玩游戏。游戏共有 $N$ 个回合，在第 $k$ 个回合，Slavko 给出两个整数 $A_k$ 和 $B_k$。请你帮助 Mirko 解决以下问题：

前 $k$ 个回合中 Slavko 给出了数字 $A_1,A_2,...,A_k$ 和 $B_1,B_2,...,B_k$。将这些数两两配成 $k$ 个数对 $(A_i,B_j)$（$1 \le i,j \le k$），使得序列 $A$ 和序列 $B$ 的每一个数都只在这些数对中出现一次，并且使所有数对的和（$A_i + B_j$）的最大值最小。

输入格式

第一行包含一个整数 $N$，表示游戏的回合数。

接下来 $N$ 行的第 $i$ 行包含两个整数 $A_i,B_i$，表示 Slavko 在第 $i$ 个回合中给出的两个数字。

输出格式

输出 $N$ 行，第 $i$ 行表示第 $i$ 个回合最小的最大数对和。

3
2 8
3 1
1 4

10
10
9

3
1 1
2 2
3 3

2
3
4

提示

【数据范围】

对于 $50\%$ 的数据，$1 \le N \le 200$。

对于 $100\%$ 的数据，$1 \le N \le 10^5$，$1 \le A_i,B_i \le 100$。

【说明】

本题分值按 COCI 原题设置，满分 $100$。

题目译自 COCI2009-2010 CONTEST #1 T4 MALI。