To organize the upcoming CCC, Troy is creating test data for the problems! The test data for one question consists of a list of $N$ integers $a_1,\dots ,a_N$. Unfortunately, the CCC Grader requires that test cases be manually entered into the system. Troy knows that this will be really tedious, so he starts right away.

However, the CCC Grader has another weird bug! When Troy submits the test case, the system scans the list in order from left to right. Whenever it comes across an integer $d$, the offending integer and the previous $x_d$ integers are removed from the test case. If there are less than $x_d$ integers currently preceding the offending integer, all integers before the offending integer are removed.

Knowing that this year's CCC is in jeopardy, Troy asks you to perform the following task: For each possible value of $d$ from $1$ to $K$, can you determine the sum of the integers in the resulting test case?

Constraints

$2\le K\le N\le {10}^6$

$1\le a_i\le K$

$1\le x_i\le N$

Subtask 1 [20%]

$N\le 2\times {10}^3$

Subtask 2 [40%]

$x_i=1$

Subtask 3 [40%]

No additional constraints.

Input Specification

The first line of input contains two integers $N$ and $K$.

The next line contains $N$ integers $a_1,\dots ,a_N$.

The next line contains $K$ integers $x_1,\dots ,x_K$.

Output Specification

Output $K$ lines, where the $k^{\text{th}}$ line is the sum of the integers in the resulting test case if $d=k$.

Sample Input 1

5 3
3 2 1 3 1
1 2 1

Sample Output 1

3
5
3

Explanation for Sample 1

When $d=1$, we have $x_1=1$. We'll denote the resultant test case as a list $b$. Initially $b=[3,2,1,3,1]$.

At $i=3$, $a_3=1=d$ so we remove $d$ and the preceeding element from $b$. $b$ now becomes $[3,3,1]$

At $i=5$, $a_5=1=d$ so we remove $d$ and the preceeding element from $b$. $b$ now becomes $[3]$

$b=[3]$ has a sum of $3$ so this is our answer when $d=1$.

Sample Input 2

10 5
2 4 4 1 3 2 2 3 1 4
2 1 2 3 8

Sample Output 2

11
16
11
6
26