G. M & Nim
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Near and Mello have just returned from trick-or-treating. Always trying to outdo each other, they decide to combine their haul and settle things with a game.

The rules are simple:

  • There are $$$1 \le n \le 10^6$$$ candies lined up in a row.
  • Near and Mello take turns picking candies, with Near going first.
  • On each turn, a player must take between 1 and 4 candies from the right end of the line.

Both know exactly how much enjoyment (or displeasure) each candy would bring them, as well as how much it would bring the other. They play optimally, each aiming to maximize their own total enjoyment. Being rivals, if multiple moves yield the same personal outcome, they'll choose the one that hurts the other the most.

Output the final total enjoyment of Near and Mello once the game concludes.

Input

The first line contains an integer $$$n$$$ ($$$1 \le n \le 10^6$$$) — the number of candies.

The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$-10^3 \le a_i \le 10^3$$$), where $$$a_i$$$ is the enjoyment Near gains from the $$$i$$$-th candy.

The third line contains $$$n$$$ integers $$$b_1, b_2, \dots, b_n$$$ ($$$-10^3 \le b_i \le 10^3$$$), where $$$b_i$$$ is the enjoyment Mello gains from the $$$i$$$-th candy.

Output

Two integers — the total enjoyment of Near and Mello after the game.

Example
Input
5
2 4 -3 -3 4
3 -5 2 4 1
Output
10 6
Note

In the sample test case, it can be shown Near will take one, Mello will take two, and Near will take two again, in that order. Thus, Near gets an enjoyment of 4 + 4 + 2 = 10, while Mello gets an enjoyment of 4 + 2 = 6.