Background

Original link: https://oier.team/problems/X1C.

Problem Description

Given a sequence $a$ of length $n$. Define its prefix sum array $b_i=\sum_{j=1}^i a_j$. Define its value $S=\sum_{i=1}^n (b_i \bmod 2)$.

You may perform the following operation on sequence $a$ any number of times:

• Swap $a_i$ and $a_j$, costing $(c_i+c_j)$ yuan, where $c$ is a given sequence.

For $i=0\sim n$, find the minimum cost to make $S=i$. If it is impossible, output $-1$.

Input Format

This problem contains multiple test cases.

The first line contains a positive integer $T$, the number of test cases.

For each test case:

The first line contains a positive integer $n$, the length of the sequence.

The second line contains $n$ positive integers, the sequence $a$.

The third line contains $n$ positive integers, the sequence $c$.

Output Format

For each test case:

Output one line with $n+1$ integers. The $i$-th integer denotes the minimum cost to make $S=i-1$. If it is impossible, output $-1$.

3
3
1 2 3
1 1 1
5
1 2 3 4 5
2 5 3 6 4
10
1 8 3 5 2 6 3 4 6 2
3 2 7 1 8 2 5 8 3 1

-1 2 0 -1
-1 -1 7 0 9 -1
-1 -1 5 3 4 0 7 8 6 -1 -1

Hint

[Sample Explanation]

For the first test case, initially $\sum_{i=1}^n (b_i \bmod 2)=2$, so the minimum cost to make $S=2$ is $0$ yuan.

Swapping $a_1$ and $a_2$ makes $\sum_{i=1}^n (b_i \bmod 2)=1$, so making $S=1$ can cost $2$ yuan. It can be proven that this is optimal.

It can be proven that there is no swapping plan that makes $S=0$ or $S=3$.

[Constraints]

This problem uses bundled testdata.

For $100\%$ of the testdata: $1\leq n,\sum n\leq 500$, $1\leq a_i\leq 10^9$, $1\leq c_i\leq 10^6$, $1\leq T\leq 500$.

Translated by ChatGPT 5