Sequence Prefix Parity Reordering

We are given a sequence (a_1,a_2,\dots,a_n) of integers and another sequence (c_1,c_2,\dots,c_n) representing costs. Define the prefix sums (b_i = \sum_{j=1}^i a_j) and the weight (S = \sum_{i=1}^n (b_i \bmod 2)). Note that only the parity of each (a_i) matters. In other words, if we define (p_i = a_i\bmod2) then (b_i \bmod2 = (p_1+p_2+\cdots+p_i)\bmod2).

You are allowed to perform as many operations as you wish. In each operation, you may choose two indices (i) and (j) and swap (a_i) with (a_j) at a cost of (c_i+c_j) (note that (c) is given). A swap operation exchanges the elements at two positions. Since swapping only rearranges the sequence, the multiset of (p_i) values is preserved. Let (k) be the number of ones in the sequence (p). Thus any reordering must have exactly (k\nones.\n\nFor any binary sequence (q_1,q_2,\dots,q_n) with exactly (k) ones (where each (q_i) is either 0 or 1), if we define the new prefix parity (r_i=(q_1+q_2+\cdots+q_i)\bmod2) then the weight becomes (S=\sum_{i=1}^{n} r_i). Your task is: for every integer (T \in {0,1,\dots,n}), compute the minimum total cost needed (by swapping elements) so that the resulting sequence (after possibly reordering (a)) has weight (S=T). If it is impossible to achieve a weight of (T), output (-1) for that (T).

Note on cost calculation: When swapping two elements, if a position (i) eventually ends up with a number whose parity is different from the original (a_i\bmod2), then that position contributes (c_i) to the overall cost. In any valid reordering leading to the target, the total cost will be the sum of (c_i) over all positions where the target parity differs from the original parity. It is not hard to see that if we let \n\n[A = { i \mid p_i=1 \text{ but target } q_i=0 }\n] [B = { i \mid p_i=0 \text{ but target } q_i=1 }\n] then the cost of swapping is (\sum_{i\in A} c_i + \sum_{i\in B} c_i), and the feasibility requires that the number of ones remains (k).

The problem now reduces to choosing a binary sequence (q) of length (n) with exactly (k) ones, so that the weight, computed as [ S = \sum_{i=1}^n r_i \quad\text{with}\quad r_i = (r_{i-1}+q_i) \bmod2\quad (r_0=0), ] equals (T), while minimizing the total cost of positions where (q_i) differs from (p_i).

inputFormat

The input consists of three lines:

• The first line contains a single integer \(n\) \( (1 \leq n \leq \text{small})\) representing the length of the sequences.
• The second line contains \(n\) space-separated integers \(a_1,a_2,\dots,a_n\).
• The third line contains \(n\) space-separated integers \(c_1,c_2,\dots,c_n\), where \(c_i\) represents the cost associated with index \(i\).

Note that only the parity of \(a_i\) matters.

outputFormat

Output (n+1) space-separated integers. The (i)-th integer (0-indexed, corresponding to target weight (T=i)) should be the minimum total cost required to reorder the sequence so that its weight (S=T), or (-1) if it is impossible.

sample

3
1 0 1
1 2 3

-1 3 0 -1