Problem J
Jouer avec moi?

Gelbteddy has an even number $N$ of toys lined up in a row, numbered $0, 1, 2, \dots , N - 1$. Toy $i$ has exactly one buddy toy, which is toy $(i \texttt{XOR} 1)$, where $\texttt{XOR}$ is the bitwise XOR operation.

Gelbteddy wants to host a show with these toys, and he must pick exactly $K$ toys for the show. The excitement value of the show depends on the selection of the toys, determined as follows:

• If toy $i$ appears in the show and its buddy toy also appears in the show, toy $i$ contributes $A_i$ of excitement value.

• If toy $i$ appears in the show and its buddy toy does not appear in the show, toy $i$ contributes $B_i$ of excitement value.

• The excitement value of the show is the sum of all excitement values contributed by the selected toys.

It is also known that $A_i \le B_i$ for all toys.

Help Gelbteddy find the maximum excitement value of his show for all possible choices of $K$!

Input

The first line of input contains one integer $N$ $(1 \leq N \leq 2 \times 10^5)$, the number of toys. It is guaranteed that $N$ is even.

The next $N$ lines of the input contains two integers $A_i$ and $B_i$ $(1 \le A_i \le B_i \le 10^9)$. The $(i+2)$-th line of the input corresponds to toy $i$ (as toys are indexed from $0$ to $N-1$).

Output

Output $N$ integers, the $i$-th integer representing the maximum excitement value when Gelbteddy chooses $i$ toys for his show.

6
3 6
4 10
5 5
5 12
1 7
8 9

12 22 31 31 29 26