Two players, ~A~ and ~B~, are playing a game on a row of ~N~ coins, each with a positive integer value ~a_i~. Player ~A~ goes first and can take any coin. Then, player ~B~ must take a coin adjacent to the coin that ~A~ chose, or must skip his turn if there are no coins adjacent to the spot that ~A~ chose. The players then alternate turns, where ~A~ can always take any remaining coin but ~B~ must take a coin adjacent to the spot ~A~ just chose or skip his turn if this is not possible. The game ends when all the coins are taken by one of the two players. Both players want to maximize the total sum of the values of the coins they have at the end.

The players will play the game ~Q+1~ times, where after each game all the coins are returned to their original positions in the row and a new coin with value ~b_i~ is added to the right end of the row.

Assuming they play optimally, calculate the total sum that player ~A~ will get in each game.

Constraints

~1 \le a_i \le 10^9~ and ~1 \le b_i \le 10^9~ for all ~i~.

Subtask 1 [10%]

~1 \le N \le 20, Q = 0~

Subtask 2 [10%]

~1 \le N \le 200, Q = 0~

Subtask 3 [10%]

~1 \le N \le 200, 0 \le Q \le 200~

Subtask 4 [15%]

~1 \le N \le 2\,000, Q = 0~

Subtask 5 [15%]

~1 \le N \le 2\,000, 0 \le Q \le 2\,000~

Subtask 6 [20%]

~1 \le N \le 200\,000, Q = 0~

Subtask 7 [20%]

~1 \le N \le 200\,000, 0 \le Q \le 200\,000~

Input Specification

The first line contains two space-separated integers: ~N~ and ~Q~.

The second line contains ~N~ space-separated integers: ~a_1, a_2, \dots, a_N~.

The third line contains ~Q~ space-separated integers: ~b_1, b_2, \dots, b_Q~.

If ~Q = 0~, the third line is empty.

Output Specification

Output ~Q+1~ lines: the total sum that player ~A~ will get in each game.

Sample Input 1

5 1
3 1 4 2 5
6

Sample Output 1

12
13

Explanation for Sample Output 1

Here is one way the first game could proceed:

• First, player ~A~ takes the coin with a value of ~4~.
• Then, player ~B~ must take either the coin with value ~1~ or the coin with value ~2~. He decides to take the coin with value ~2~.
• Then, player ~A~ takes the coin with value ~5~. There are no untaken coins adjacent to this coin, so player ~B~ must skip his turn.
• Finally, player ~A~ takes the coin with value ~3~. Player ~B~ must take the only remaining coin with value ~1~, and the game ends with ~A~ getting a total sum of ~4+5+3 = 12~.

The second game is played on the row ~[3,1,4,2,5,6]~, and player ~A~ can get a total sum of ~13~ if both players play optimally.

Sample Input 2

10 0
27 18 28 18 28 45 90 45 23 53

Sample Output 2

243