E. Eat Economically
time limit per test
3 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Ho has arrived in a secret place for her secret business trip. She knows her trip will take at most N days or shorter but doesn't know the exact number of days she'll be there. So, the perfectionist Ho wants to make the daily meal lists for every possible trip length, 1 day to N days.

There is the only food court that offers exactly 2N kinds of menus (by accident) in this secret place. The food court opens only lunch time and dinner time, and oddly, the prices of lunch and dinner for the same menu can be different.

She will eat exactly one menu per lunch and dinner respectively and never eat the same menu for the entire of the trip. She never minds about which kind of menu will be her meal, the only important thing is the entire price of meals must be minimized.

Under these conditions, she can make her meal lists but realizes that writing every N(N + 1) menu is hard and tiresome. So, instead of making the meal lists, she calculates the minimized entire price for i lunch menus and i dinner menus where i = 1 to N.

You, the big fan of Ho, has a supreme task. Print the N prices she calculated.

Input

The first line contains an integer N. (1 ≤ N ≤ 250000)

In the next 2N lines, each line contains two integer l, d denoting the prices of the menus when lunch and dinner respectively. (1 ≤ l, d ≤ 109)

Output

Print N lines. The i-th line should contain an integer denoting the minimized entire price for i lunch menus and i dinner menus.

Examples
Input
1
4 9
5 3
Output
7
Input
2
1 6
2 4
5 3
3 1
Output
2
7
Input
4
7 5
5 7
7 4
4 2
2 5
6 4
3 2
1 9
Output
3
7
16
26