鼹鼠通过隧道在它们的洞穴之间穿行。在本题中，我们研究一个由鼹鼠建造的隧道系统。该系统由 $n$ 个洞穴和连接它们的 $n-1$ 条隧道组成。我们将所有洞穴编号为 $1$ 到 $n$。对于所有 $i > 1$，洞穴 $i$ 通过一条隧道与洞穴 $\lfloor \frac{i}{2} \rfloor$ 相连。隧道是双向的。对于每个洞穴 $i$，我们已知该洞穴中食物的数量 $c_i$，这意味着该洞穴中最多能容纳 $c_i$ 只鼹鼠进食。

隧道系统中住着 $m$ 只鼹鼠。对于每只鼹鼠 $i$，给定一个整数 $p_i$，表示鼹鼠 $i$ 当前所在的洞穴。早晨，前 $k$ 只鼹鼠醒来并想要进食，而其余 $m-k$ 只鼹鼠仍在睡觉。每只醒来的鼹鼠都会选择一个洞穴并爬过去。它们非常聪明，因此希望最小化总移动距离。一只鼹鼠移动的距离是它从一个洞穴到达另一个洞穴所经过的隧道总数。前 $k$ 只醒来的鼹鼠希望以这样一种方式移动：它们选择的洞穴中有足够的食物供它们进食。这意味着在所有移动结束后，洞穴 $i$ 中醒来的鼹鼠数量不超过 $c_i$。

你需要求出对于所有 $k$ 从 $1$ 到 $m$ 的最小总距离。题目保证对于所有 $k$，总存在一种让所有鼹鼠都能进食的方案。

输入格式

第一行包含两个整数 $n$ 和 $m$ ($1 \le n, m \le 10^5$)，分别表示洞穴和鼹鼠的数量。 第二行包含 $n$ 个整数 $c_i$ ($0 \le c_i \le m$)，表示洞穴 $i$ 中的食物数量。 第三行包含 $m$ 个整数 $p_i$ ($1 \le p_i \le n$)，表示鼹鼠的起始位置。

输出格式

输出 $m$ 个数字。第 $k$ 个数字表示前 $k$ 只醒来的鼹鼠需要移动的最小总距离。

样例

输入 1

5 4
0 0 4 1 1
2 4 5 2

输出 1

1 1 2 4

说明

上图中的虚线箭头展示了使总距离最小化的醒来鼹鼠的可能移动路径。例如，当 $k=2$ 时，第一只鼹鼠从洞穴 2 移动到洞穴 5，第二只鼹鼠留在洞穴 4。