A card game renowned as a test of intellect is called “Kang”. In this game, each card has a positive integer score. At the start, you receive $N$ cards to hold in your hand, and there are another $M$ cards placed face up on the table arranged from left to right. You can see the score of every card, both those received in your hand and those placed on the table. Then, you may draw additional cards from the table for $k$ rounds, picking one card at a time from left to right. After each round of drawing a card, you may discard cards from your hand once, removing any number of cards in your hand that have the same score. You must plan your play so that after drawing cards from the table and discarding cards from your hand for all $k$ rounds, the remaining cards in your hand have the minimum possible total score.

Consider the following example.

Suppose at the start you have five cards with scores $6, 3, 9, 6, 3$, and the cards placed on the table have scores from left to right $4, 6, 9, 6$.

Case $k = 1$: If you can draw only 1 card from the table, when you draw the first card, the scores of the cards you have will be $6, 3, 9, 6, 3, 4$. Then you can choose to discard cards with the same score once. The best choice is to discard 2 cards with score $6$, so that the total score of the remaining cards is minimized at $3 + 9 + 3 + 4 = 19$.

Case $k = 2$: If you can draw 2 cards from the table, the best strategy is: after drawing the first card with score $4$, you choose to discard one card with score $9$. The remaining cards in your hand have scores $6, 3, 6, 3, 4$. Then, when you draw the 2nd card with score $6$, you can discard 3 cards with score $6$, leaving the remaining cards with the minimum total score of $3 + 3 + 4 = 10$.

Case $k = 3$: If you can draw 3 cards from the table, the best strategy is: when you draw the first card, the scores of the cards in your hand will be $6, 3, 9, 6, 3, 4$. Then you choose to discard cards with the same score once. The best choice is to discard both 2 cards with score $3$, leaving $6, 9, 6, 4$ in your hand. Next, when you draw the 2nd card with score $6$, you can discard 3 cards with score $6$, leaving $9, 4$ in your hand. And when you draw the 3rd card with score $9$, you can discard both 2 cards with score $9$, leaving the remaining card with a total score of $4$.

Case $k = 4$: If you can draw 4 cards from the table, the best strategy is: after drawing the first card with score $4$, choose to discard one card with score $4$, leaving cards in your hand with scores $6, 3, 9, 6, 3$. Next, on the 2nd draw, the card has score $6$; the best choice is to discard both 2 cards with score $3$, leaving $6, 9, 6, 6$ in your hand. On the 3rd draw, the card has score $9$; choose to discard both 2 cards with score $9$. Finally, when drawing the last card with score $6$, you can discard 4 cards with score $6$. This discard leaves no cards in your hand, which means the total score of the cards is $0$.

Your Task

Find the “minimum total score of the remaining cards in your hand” after finishing $k$ rounds, for $k = 1, 2, 3, \ldots, M$.

This problem uses a programming format that differs from the standard format, which is used in the actual competition. Please see the end of this problem statement for instructions on how to use it.

Implementation Details

You must implement the following function:

std::vector<long long> capsize(std::vector<int> A, std::vector<int> B)

With the following parameters:

• $A$ is an array of length $N$ specifying the numbers on the cards in your hand at the start.
• $B$ is an array of length $M$ specifying the numbers on the cards placed on the table, ordered from left to right.
• The function must return an array $C$ of length $M$ representing the minimum possible total score of the cards in your hand after $k$ rounds, for $k = 1, 2, 3, \ldots, M$.

For example, if $A = [6, 3, 9, 6, 3]$ and $B = [4, 6, 9, 6]$, the function must return the array $[19, 10, 4, 0]$.

Constraints

• $1 \le N, M \le 10^6$
• $1 \le A[i] \le 10^9$ for each $i$ where $1 \le i \le N$
• $1 \le B[i] \le 10^9$ for each $i$ where $1 \le i \le M$

Subtasks

Note

Programming Instructions

For this problem, the method of writing and submitting your program to the grading system (Grader) differs from the usual format where contestants must write code for reading input and printing output. In this problem, contestants only need to write the necessary computation inside the specified function. All input data is provided through the function's parameters, and the computed result must also be returned via the function. Contestants must not write code to read input or print output.

Contestants will receive several files as follows. Contestants must modify only the single file specified by the problem and submit that file to the system:

• grader.cpp is the main file responsible for reading input and writing output.
• kang.cpp is the file where contestants must write the computation code, and is the file contestants submit to the system (in kang.cpp, there must not be a main() function, but other helper functions are allowed).
• run_cpp.sh is a script that contestants can run to execute the entire program.
• compile_cpp.sh is a script that contestants can run to compile the program.

Contestants will receive a .zip archive downloadable from the system; when extracted, it contains all 4 files. Contestants should use a text editor or IDE to edit kang.cpp, and compile or run the program by invoking compile_cpp.sh or run_cpp.sh.

When contestants run run_cpp.sh to execute the program, the program will operate as specified in grader.cpp, whose behavior is described in the “Grader File Description” section.