The problem statement has recently been changed. View the changes.

×
E. Eat Economically

time limit per test

3 secondsmemory limit per test

1024 megabytesinput

standard inputoutput

standard outputHo 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 2*N* 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 2*N* lines, each line contains two integer *l*, *d* denoting the prices of the menus when lunch and dinner respectively. (1 ≤ *l*, *d* ≤ 10^{9})

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

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Sep/27/2021 14:09:56 (f1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|