题目背景

X2H 在上信竞课时，每天中午机房里的有几个懒狗（刷题出不来的 dalao）叫我这个 juruo 帮他们订餐。

题目描述

餐厅提供 $n$ 种餐，每种餐最多只能订一份，还有一个有趣的定价政策：每种餐有两个指定的价格，$A_i$ 和 $B_i$。当天购买的第一种餐需要花费价格 $A$，其他餐则只需要花费价格 $B$。

X2H 每天都帮人订餐，但他不知道自己要订几种，于是他想知道购买 $1 \sim n$ 种餐的最小花费。请你帮他算一下。

输入格式

输入的第一行包含一个正整数 $n$，餐厅提供的餐的种类数。

接下来 $n$ 行每行包含两个正整数，$A_i$ 和 $B_i$，表示第 $i$ 种餐的两个价格。

输出格式

输出共 $n$ 行，第 $i$ 行输出订 $i$ 种餐的最小花费。

3
10 5
9 3
10 5

9
13
18

2
100 1
1 100

1
2

5
1000000000 1000000000
1000000000 1000000000
1000000000 1000000000
1000000000 1000000000
1000000000 1000000000

1000000000
2000000000
3000000000
4000000000
5000000000

提示

对于 $100\%$ 的数据：

• $2 \le n \le 5 \times 10^5$
• $1 \le A_i,~B_i \le 10^9$