Description

现在有一棵n个结点的树，对于点i(i>1)，它的父亲结点编号为trunc(i/2)。

现在有m只鸟，每只鸟有初始位置pi。树上每个结点有最大容纳量ci，表示这个结点最多能容纳的鸟的数量。

定义移动一只鸟的代价为树上的距离。

现在询问，对于k从1∼m，将前k只鸟移动位置使得满足每个结点上的鸟的个数不大于最大容纳量的最小代价。

Format

Input

第一行两个用空格隔开的整数n,m。n, m ≤ 3 × 10^5 第二行n个整数表示c1,c2,···,cn。 第三行m个整数表示p1,p2,···,pm。

Output

输出一行，表示对于每个k的最小代价。

Samples

5 4 
0 0 4 1 1
2 4 5 2

1 1 2 4
第一只鸟在 2 上，只需移到 4 或 5 即可，代价为 1。
第一、二只鸟在 2,4 上，第一只鸟移到 5，第二只鸟不动，代价为 1。
第一、二、三只鸟在 2, 4, 5 上，第一只鸟移到 3，第二、三只鸟不动，代价为 2。
第一、二、三、四只鸟在 2, 4, 5, 2 上，第一、四只鸟移到 3，第二、三只鸟不动，代价为 4。