Underground Mole Tunnels

Moles have carved out \(n\) holes underground which are connected by \(n-1\) tunnels. For every hole with index \(i>1\), there is a tunnel between hole \(i\) and hole \(\lfloor i/2\rfloor\). Each hole \(i\) contains \(c_i\) units of food, which can feed at most \(c_i\) moles.

There are \(m\) moles in total. The \(i\)th mole lives in hole \(p_i\). One morning, the first \(k\) moles (for a given \(1 \le k \le m\)) wake up while the rest remain asleep. All awake moles then set out to find food and eventually converge to a single meeting hole. The chosen meeting hole \(j\) must satisfy the condition that the number of awake moles arriving at it does not exceed \(c_j\) (i.e. \(c_j \ge k\)).

The moles travel along the tunnels; the distance between adjacent connected holes is 1. Their objective is to choose a meeting hole \(j\) (subject to \(c_j \ge k\)) so that the total traveling distance, which is equal to \(\sum_{i=1}^{k} \text{dist}(p_i,j)\), is minimized. For each \(k\) from 1 to \(m\), compute the minimum total travel distance.

Note: It is guaranteed that for every \(1\le k\le m\) there exists at least one hole \(j\) satisfying \(c_j \ge k\>.

inputFormat

The first line contains two integers \(n\) and \(m\) representing the number of holes and the number of moles, respectively.

The second line contains \(n\) integers: \(c_1, c_2, \dots, c_n\), where \(c_i\) is the food capacity of the \(i\)th hole.

The third line contains \(m\) integers: \(p_1, p_2, \dots, p_m\), where \(p_i\) is the starting hole of the \(i\)th mole.

outputFormat

Output \(m\) integers separated by spaces. The \(k\)th integer represents the minimum total travel distance for the first \(k\) moles to converge to a meeting hole that can feed all of them (i.e. a hole \(j\) with \(c_j \ge k\)).

sample

3 3
2 1 3
1 2 3

0 1 3