题目描述

鼹鼠们在底下开凿了 $n$ 个洞，由 $n-1$ 条隧道连接，对于任意的 $i>1$，第 $i$ 个洞都会和第 $\frac{i}{2}$（取下整）个洞间有一条隧道，第 $i$ 个洞内还有 $c_i$ 个食物能供最多 $c_i$ 只鼹鼠吃。一共有 $m$ 只鼹鼠，第 $i$ 只鼹鼠住在第 $p_i$ 个洞内。

一天早晨，前 $k$ 只鼹鼠醒来了，而后 $m-k$ 只鼹鼠均在睡觉，前 $k$ 只鼹鼠就开始觅食，最终他们都会到达某一个洞，使得所有洞的 $c_i$ 均大于等于该洞内醒着的鼹鼠个数，而且要求鼹鼠行动路径总长度最小。现对于所有的 $1 \le k \le m$，输出最小的鼹鼠行动路径的总长度，保证一定存在某种合法方案。

输入格式

第一行两个数 $n,m$，表示有 $n$ 个洞，$m$ 只鼹鼠。 第二行 $n$ 个整数 $c_i$ 表示第 $i$个洞的食物数。 第三行 $m$ 个整数 $p_i$ 表示第 $i$只鼹鼠所在洞 $p_i$。

输出格式

输出一行 $m$ 个整数，第 $i$ 个整数表示当 $k=i$ 时最小的鼹鼠行动路径总长度。

5 4
0 0 4 1 1
2 4 5 2

1 1 2 4

提示

$1 \le n,m \le 10^5$，$0 \le c_i \le m$，$1 \le p_i \le n$。