Mr. Purple has a class of $M$ students, who are numbered from $1$ to $M$, and he is preparing a test with $N$ questions for them. The questions on the test are in non-decreasing order of points, and all carry a specific weight in points, where the $i$-th question is worth $A_i$ points.

Known for his leniency during tests, Mr. Purple often does not watch the students, allowing them to sneakily google the answers on their phones. Unfortunately (for the students), he has a scheme in place to prevent cheating. For the $i$-th question, Mr. Purple estimates that $B_i$ students will correctly answer it. If more students solve a question than expected, Mr. Purple will believe the students have been cheating and will be forced to investigate.

Thankfully, after some clever social engineering from one of the brightest students (you), all the weights of the questions and Mr. Purple's estimations have been uncovered. Now, the night before the test, the class has agreed their strategy will be the following:

Going through the test in order, for the $i$-th question, the $B_i$ students with the lowest score so far will put down the correct answer, while the others put down incorrect answers. If there are ties, the students numbered with smaller student numbers take priority.

Your goal is to determine what the scores of each of the students will be on the test.

Constraints

$2\le N,M\le {10}^6$

$1\le A_i\le {10}^9$

$A_1\le A_2\le \dots \le A_N$

$1\le B_i\le M$

Subtask 1 [20%]

$A_i=1$

Subtask 2 [80%]

No additional constraints.

Input Specification

The first line of input contains two integers $N,M$, the number of questions and the number of students respectively.

The second line of input contains $N$ integers $A_1,A_2,\dots ,A_N$, the number of points the $i$-th question is worth.

The third line of input contains $N$ integers $B_1,B_2,\dots ,B_N$, the number of students that are expected to solve the $i$-th question.

Output Specification

Output $M$ integers, where the $i$-th integer is the final score of student $i$.

It is possible for these values to exceed the limits of a 32-bit integer. It is advised to use 64-bit integers instead, meaning that Java users should use long, and C++ users should use long long.

Sample Input 1

3 2
1 2 3
1 2 2

Sample Output 1

6 5

Explanation for Sample 1

Initially, the scores are $[0,0]$.

The first problem will be solved by only student #1. Hence, the scores will become $[1,0]$.

Both the second and third problem will be solved by both students. Thus, the final scores will be $[6,5]$.

Sample Input 2

5 6
1 2 2 7 8
3 1 4 1 5

Sample Output 2

11 11 8 10 10 10